Question

Let S = (s1, s2, . . . , sn) be a given sequence of integer numbers. The numbers can be positive or negative. We define a slice of S as a sub- sequence (si,si+1,...,sj) where 1 ≤ i < j ≤ n. The weight of a slice is defined as the sum of its elements. Provide efficient algorithms to answer each of the following questions:

a)Is there any slice with zero weight ?
b)Find the maximum weight slice in the sequence.

Answer 1

a) Is there any slice with zero weight ?

Time Complexity : O(N).

b) Find the maximum weight slice in the sequence.

Algorithm is self explanatory with code :

    int max_sum = 0;
    int current_sum = 0;
    for(int i = 0; i < N; i++)
    {
        current_sum += S[i];
        if(current_sum > max_sum)
            max_sum = current_sum;
        if(current_sum < 0)
            current_sum = 0;
    }
    cout<<max_sum<<"\n";

Time Complexity : O(N).

Like, if this helped :)