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;imax_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;isum+a[i])                 sum=sum+a[i];       else       {               if(max_summax_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   Fog Creek Home