massimo subarray

[CuriousCI]

Dato in input un array $A$ di interi (quindi anche valori negativi) scrivere lo pseudocodice di un algoritmo che trova un subarray $A[i, j], i \leq j$ (una porzione dell'array che va da $i$ a $j$) di somma massima, e ne ritorna la somma in $O(n log(n))$

[CuriousCI]

Dovrebbe funzionare, fatemi sapere se c'è qualcosa di strano

fn max_subarray(vec: &[isize]) -> isize {
    if vec.len() == 1 {
        return vec[0].max(0);
    }

    fn max<'a>(x: impl Iterator<Item = &'a isize>) -> isize {
        x.scan(0, |acc, &x| {
            *acc += x;
            Some(*acc)
        })
        .max()
        .unwrap()
    }

    let middle = vec.len() / 2;

    let prefix = max(vec[..middle].iter().rev());
    let suffix = max(vec[middle..].iter());

    (prefix + suffix)
        .max(max_subarray(&vec[..middle]))
        .max(max_subarray(&vec[middle..]))
}

[interestingmaneuver]

Si può notare che max opera sulla porzione che verrà poi esaminata dalle sottochiamate, quindi puoi restituire i valori intermedi per far scendere la complessità a $O(n)$:

fn max_subarray(vec: &[isize]) -> (isize, isize, isize, isize) {
    if vec.len() == 1 {
        return (vec[0], vec[0], vec[0], vec[0]);
    }

    let middle = vec.len() / 2;
    
    let (left_sol, left_sum, left_pref, left_suff) = max_subarray(&vec[..middle]);
    let (right_sol, right_sum, right_pref, right_suff) = max_subarray(&vec[middle..]);

    let sol = right_sol.max(left_sol).max(left_suff + right_pref);
    (
        sol, 
        left_sum + right_sum, 
        left_pref.max(right_pref + left_sum),
        right_suff.max(left_suff + right_sum)
    )
}

[CarloDaRomadev]

def massimo_subarray(a : array){
	n = len(a)
	m = n/2
	if n == 0{
		return 0
	}
	if n == 1{
		return a[0]
		
	L = massimo_subarray(a[0:m])
	R = massimo_subarray(a[m+1,n-1])
	S = 0
	for i da m a 0{
		somma = S + a[i]
		S = max(S,somma)
	}

	fot j da m+1 a n-1{
		somma = S + a[j]
		S = max(S,somma)
	}
	return max(R,L,S)
}

[CarloDaRomadev]

Equazione di ricorrenza:
T(n) = 2T(n/2) + f(n).
a = 2, b = 2, k = 0
f(n) = [n ^ (log_2(2))]*[log(n)]^k -> T(n) = n(log(n))