Antonio Mario Caruso

[7/06/2011]

1. Segmento di somma massima di un vettore.

Soluzione di complessità cubica:

int CalcolaIntervalloMassimo(int v[], int n,  int *start, int *end)
{
    int l=0,u=0,i=0;
    int somma=0;
    sommamax = INT_MIN;
    for (l=0; l<n; l++)
        for (u=l; u<n; u++)
        {
            somma = 0;
            for (i=l; i<u; i++)
                somma = somma + v[i];
            if (sommamax < somma)
            {
                sommamax = somma;
                low = l;
                upper = u;
            }
        }
    *start = low; *end = upper; return sommamax;
}

Soluzione di Complessità Lineare:

int CalcolaIntervalloMassimo(int v[], int n, int *start, int *end)
{
    int sum = 0, max = 0;
    int s = 0, e = 0;
    for (int i=0; i<n; i++)
    {
        sum += v[i];
        if (sum < 0) { s = i+1; sum = 0; }
        else
            if (sum > max) { e = i; max = sum; }
    }
    *start = s; *end = e;
    return max;
}