Fog Creek Software
Discussion Board




Maximum Sub array problem

Given an array of positive and negative numbers. Here job is to find the subarray of maximum sum.

#define N 10
int a[N]={1,-2,3,-1,-5,2,4,-11,7,-9};
int sum=0,max_sum=0;
int index1,index2;

for(i=0;i<N;sum=0,i++){

    for(j=i;j<N;j++){
            sum=sum+a[j];
           
            if(sum>max_sum){
                              max_sum=sum;
                                index1=i;
                                index2=j;
            }
      }

The Complexcity is O(n2). Can any one suggest some goog algo ??

}

Biswajit Paul
Thursday, May 05, 2005

sum = 0;
max = sum;
for (i=0;i < N; i++) {
  sum += a[i];
  if (sum < 0) sum = 0;
  if (sum > max) max = sum;
}

This presumes that you're allowed to sum the empty sequence.  If that's not allowed, initialize max to a[i], and move the if (sum<0) statement after if (sum > max).

Anonymous
Friday, May 06, 2005

Hi,

It looks like O(n) solution will have the following variables:

int currentIndex = -1;
int currentSum = 0;
int currentMin = 0;
int indexMin = -1;
int bestFrom = -1;
int bestTo = -1;
int bestSum = 0;

DK
Tuesday, May 10, 2005

isn't it as simple as taking all positive numbers (>0) from the array. i.e i can simply replace all -ve entries by 0, in case a new storage is an issue. This will give a sub array (so i guess a new storage is needed ... without any 0 as 0 will not make new array as sub array) with max positive sum.

gitesh malik
Monday, May 16, 2005

Hi, Gitesh

You solution is right for the problem as it is stated.

The thing is - Biswajit's code looks for a continuous subsequence i..j within original array 0..N-1, not a subset of original array elements. Because of this, and because it is too simple to get a subset - my assumption was that the problem is to find a continuous subsequence.

DK
Monday, May 16, 2005

my algo is
sum=max_sum=0;
index1=0;
max_index1=max_index2=0;
for(i=0;i<n;i++)
{
      if(sum>sum+a[i])
                sum=sum+a[i];
      else
      {
              if(max_sum<sum)
              {
                    max_sum=sum;
                    max_index1=index1; 
                    max_index2=i;
                    index1=i; 
              }
              index1+=1;
        }
}
if(sum>max_sum)
print(sum,index1,i);
else
print(max_sum,max_index1,max_index2);
             

thahir
Monday, May 16, 2005

hi friends,
  I guess there is some mistake in understaning the problem.I guess DK has understood it correctly. Its a continious SUB-SEQUENCE(may have both +ive and  -ive entries) which gives the MAX SUM. 

Biswajit Paul
Tuesday, May 24, 2005

Use this one :
int maxSubSum3( int [ ] a )
    {
        int maxSum = 0;
        int thisSum = 0;
        int i=0;
        int j=0;

        while (j < a.length)
        {
            thisSum =thisSum + a[ j ];

            if( thisSum > maxSum )
            {
                maxSum = thisSum;
                seqStart = i;
                seqEnd  = j;
            }
            else if( thisSum < 0 )
            {
                i = j + 1;
                thisSum = 0;
            }
            j=j+1;
        }

        return maxSum;
    }

Diganta Sarkar
Tuesday, June 07, 2005

*  Recent Topics

*  Fog Creek Home