Exercise 4.1-5

4.1-5 Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward the right,keeping track of the maximum subarray seen so far. Knowing a maximum subarray of A[1.. j] , extend the answer to find a maximum subarray ending at index j + 1 by using the following observation: a maximum subarray of A[1.. j + 1] is either a maximum subarray of A[1.. j] or a subarray A[i .. j +1] , for some 1 <= i<= j + 1. Determine a maximum subarray of the form A[i... j+1] in constant time based on knowing a maximum subarray ending at index j.

Answer

First we need to figure out the maximum sub array ending at index j + 1 which could be just A[j + 1] or the maximum subarray ending at j plus A[j+1] , therefore we find the max of this two.

Once we have the maximum sub array ending at index j + 1 we find the maximum of A[1..j+1] by again, getting the max between  maximum sub array ending at index j + 1 and maximum subarray of A[1..j].

Code (C++):

void linearMaxSubArray(int*& ini, int*& fin){

    int sum = ini[0], max = ini[0],
        *inisum = ini, *end= fin;

    fin = ini + 1;
    for (auto i = ini + 1; i != end; ++i)
    {
        sum = std::max(*i, *i + sum);  
        inisum = sum == *i ? i : inisum;   
        if (sum > max)
        {
            fin = i + 1;
            ini = inisum;
            max = sum;
        }
    }
   
}