Maximum Sum SubArray Problem

Maximum Subarray is well and standard algorithm.

Problem statement : You are given an array of N numbers. You need to Find a subarray such that the sum of the elements is maximum possible.

Naive solution : Find all the possible subarrays of length [0..N] and find their respective sums to get the largest array. Obviously the calculation results to O(N^2) complexity.

Pseudo Code:

function (array[]):
        declare sum[N][N] <- Initialise with 0
        sum[0][0] = a[0]
        //Using Zero-Indexed array
         for i in [1..N-1]:
                 sum[0][i] = a[i] + sum[0][i-1]

         for i in [1..N-1]:
                 for j in [0..i]:
                         sum[i][j] = array[k]

         for k in [i+1..N-1]:
                 sum[i][k] = array[i][k-1] + a[k]
         max_sum = 0
         posx = -1
         posy = -1

         for i in [0..N-1]:
                 for j in [0..N-1]:
                         if max_sum < sum[i][j]:
                                  max_sum = sum[i][j]
                                  posx = i
                                  posy = j
         print max_sum , posx, posy

C++ Implementation

//***********************************************************************

#include <bits/stdc++.h>
using namespace std;
int main()
{
 int i,j,k;
 int a[8] = {-2, -3, 4, -1, -2, 1, 5, -3}; // sample array
 int sum[9][9];
 sum[0][0] = a[0];
 for(i=1; i<8; i++)
         sum[0][i] = a[i] + sum[0][i-1];
 for(i=1; i<8; i++)
 {
          for(j=0; j<i+1; j++)
                   sum[i][j] = a[j];
          for(k=i+1; k<8; k++)
                   sum[i][k] = sum[i][k-1] + a[k];
 }
 //Prints the Sum Array
 for(i=0; i<8; printf("\n"),i++)
          for(j=0; j<8; j++)
                   printf("%d ", sum[i][j]);


 int max_sum=0, posx=-1, posy=-1;
 for(i=0; i<8; i++)
 {
          for(j=0; j<8; j++)
          {
                  if(max_sum < sum[i][j])

                 {
                           max_sum = sum[i][j];
                           posx = i;
                           posy = j;
                 }
          }
 }
 printf("%d %d %d\n",max_sum, posx, posy );
 return 0;
}
//***********************************************************************

This is a simple brute force that computes the sum array for the array [-2, -3, 4, -1, -2, 1, 5, -3] we get the sum array as

-2 -5 -1 -2 -4 -3  2 -1

-2 -3  1  0 -2 -1  4  1

-2 -3  4  3  1  2  7  4

-2 -3  4 -1 -3 -2  3  0

-2 -3  4 -1 -2 -1  4  1

-2 -3  4 -1 -2  1  6  3

-2 -3  4 -1 -2  1  5  2

-2 -3  4 -1 -2  1  5 -3

Note that the first one is the cumulative array. The second starts at a[1] and continues a cumulative array from pos 1 (zero based index) to end. Similarly the third and the fourth. This works because we want to take the sum of m elements starting from [0..N] eg:  

sum00 = -2 taking just the first element  
sum01 = -2+-3 taking 2 elements  
sum02 = -2 + -3 + 4 taking 3 elements

sum11 = -3 taking 1 elements from pos 1  
sum12 = -3 + -4 taking 2 elements from pos 1

Similarly for others... thus we have the sum of all contiguous blocks starting from 0 to N-1 Now we just need to select the sum. Also, just check out that the array was not random. Each position is the range sum for Sum[i][j] : Summation from a[i] to a[j] ,thus for the index we just need to print the indexes where the maximum was found. Time Complexity : O(N^2) Space Complexity : O(N^2)

Dynamic Programming Solution

The brute force method works but is not sufficient. In this method we use a Simple logic: Suppose we have a set MAX = {} containing the subarray and S[] storing the answer to the above problem upto index 'i' of A[] using the array A = [-2, -3, 4, -1, -2, 1, 5, -3] if S[upto i-1] + A[i] < A[i] then the solution is not optimum as we can get a subset that has sum greater than our best set till 'i'. MAX = {A[i]} now the new subset if S[upto i-1] + A[i] > A[i] then we get a subset with sum greater than the best sum subset till 'i'.

 Pseudo Code:

 dp = [max(A[i], 0] //Considering the choice of Null set or choosing the
      // first element
 for i in [1..N-1]:
         if A[i] > A[i-1] + dp[i-1]:
                   dp[i] = dp[i-1] + a[i]
   // Adding the element to the Set
         else:
                   dp[i] = a[i];
   // Reset the Sum array to new set
 max_Sum = maximum_Element in dp[]

Python Implementation:

#***********************************************************************
def max_subarray(lst):
        dp = []
        dp.append(max(lst[0],0))
        st = [0]
        end = [0]
        for i in range(1, len(lst)):
                if (lst[i] > lst[i-1]+dp[i-1]):
                        st.append(i)
                        end.append(0)
                else:
                        st.append(st[i-1])
                        end.append(end[i-1]+1)
                dp.append(max(lst[i], lst[i]+dp[i-1]))
        max_sum = max(dp)
        a = dp.index(max_sum)
        rt = (st[a], st[a]+end[a], max_sum)
        return rt
lst = map(int, raw_input().split(' '))
print max_subarray(lst)
#**********************************************************************

The above code keeps the track when the Set resets and the number of elements added getting the length of the set st[] = starting point of the set end[] = length of the set

  C++ Implementation

//*********************************************************************
#include <bits/stdc++.h>
using namespace std;
int main()
{
 int i,j,k,n,st,ed;
 scanf("%d", &n);
 int dp[n+1], mx;
 int a[1001];
 for(i=0; i<n; i++)
         scanf("%d", &a[i]);
 dp[0] = max(0, a[0]);
 st = 0; ed = 0;
 for(i=1; i<n; i++)

 {
         if(a[i] < dp[i-1]+a[i])
                 dp[i] = dp[i-1]+a[i];
         else
                 dp[i] = a[i] ,st = i;
 }

 mx = -1;
 for(i=0; i<n;i++)
         if(mx<dp[i])
                 mx = dp[i], ed = i;

 printf("Maximum Sum %d\n", mx);
 printf("Maximum Sum Subarray A[%d : %d]\n",st+1, ed+1);

 return 0;

}

//*********************************************************************

Time Complexity : O(n)
 Space Complexity : O(n) virtually no extra space