DP --- Maximum Subarray Sum

Finding maximum subarray sum

Solution1;
Since the subarray with maximum sum can happen anywhere of an array, even if we know the maximum subarrary sum for A[0]...A[n-1], we don't know how to use it to derive a maximum subarray sum for A[0]...A[n].

This problem has to think about the relation of A[0]...A[n-1] and A[0]...A[n] in terms of subarray. Suppose the sum ending at i is S[i], then when A[n] is added, the possible biggest subarray ending at A[n] is S[n] - min(S[i]) for 0<=i<=n-1. Compare it with  recording maximum subarray sum ending at A[n-1], we can get maximum subarray sum ending at A[n].

Complexity is O(N), space usage is O(1)


Solution 2:
Remeber the maximum subarray till A[i], it is max(A[i], A[i] + maximum subarry till A[i-1]) , then the maximum subarray sum is max (previous max,  maximum till A[i])

Code:
For solution 1:
pair maxsubsum(vector  &A)
{
     int Min =  0;   // min S
     int Sum = 0;   // sum S
     int Max = numeric_limit::min();   //max
     pair range(0,0);
    int idx = -1;

    for (int i=0; i   {
         Sum += A[i];
         int temp = Sum - Min;
          if (Sum < Min) {Min = Sum; idx = i;}
         if (temp > Max)
                 {Max =  temp; range = {idx+1, i+1}
    }
     return range;
}