Maximum Subarray Problem

In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. The problem was first posed by Ulf Grenander of Brown University in 1977, as a simplified model for maximum likelihood estimation of patterns in digitized images. A linear time algorithm was found soon afterwards by Jay Kadane of Carnegie-Mellon University (Bentley 1984). [Wiki]

Example:
[1] A = {-2,1,-1,1,1,-1,2,1,-5}; [assum, 1st element is indicated by 0]
Maximum Value = 4, start index = 1, End index = 7

[2] A = {-2,1,-2,1,1,-1,2,1,-5}; [assum, 1st element is indicated by 0]
Maximum Value = 4, start index = 3, End index = 7

[3] A = {-2,1,-3,4,-1,2,1,-5,-4}; [assum, 1st element is indicated by 0]
Maximum Value = 6, start index = 3, End index =6

[4] A = {2,3,5,4,6,3,5,4,6};
Maximum Value = 38, start index = 0, End index =8

[5] A = {-1,-2,-3,-4,-5,-6,-7,-8,-9}
Maximum Value = -1, start index = 0, End index =0

Explaination:
if consider sum is equal to or grater than zero, then we have to follow this algorithm:

if -infinite < sum < +infinite then we have to follow this algorithm:

How we find the range of the index:

Kadane's algorithm

[1] Iterative Solution (here max_Index and min_index is not consider here]

/*
Problem: Maximum subarray problem
Ref: https://en.wikipedia.org/wiki/Maximum_subarray_problem
Variable Defination
max_e = maximum end here
max_so = maximum so far
input range INT_MIN < = xi < = INT_MAX
*/
#include<stdio.h>

int max(int a, int b){return (a > b)?a:b;}

int main(){
   int a[] = {-2,1,-2,1,1,-1,2,1,-5};
   int N=9,i;
   int max_e,max_so;

   /*Print Array*/
   printf("Array: { ");
   for (i = 0; i<N ; i++)
            printf("%d ",a[i]);
   printf("} \n\n");


   /*Kadan's Algorithm*/
   max_e= max_so =a[0];
   for(i=1;i <N;i++){
       max_e = max(a[i], max_e + a[i]);
       max_so = max(max_so, max_e);
   }


   printf("Maximum Sum of Continuous Sub-Array: %d\n",max_so);

  return 0;
}

[2] Recursive Method:

/*
Variable Defination
N = Number of Total Element
a[] = array
GS = Global Starting Index
GE = Global End Index
CMax = Current Maxumum Sum
CSI = Current Start Index
CEI = Current End Index
Max = Final Maximum Number
Ref: http://www.algorithmist.com/index.php/Kadane%27s_Algorithm
*/
#include<stdio.h>

int GS = 0, GE =0;

int Kadane (int *a,int N,int Max){
    int CMax,CSI,CEI;

    CMax = 0;
    CSI = 0;

    for (CEI = 0; CEI < N ; CEI++){

        CMax = CMax + a[CEI];

        if(CMax > Max){
          GS  = CSI, GE = CEI;
          Max = Kadane(a,N,CMax);
        }

        if(CMax < 0) {
            CMax = 0;
            CSI = CEI + 1;
        }
    }
    return Max;
}


int main(){
    int a[] = {-2,1,-3,4,-1,2,1,-5,-4};
    int N=9,Max;
    int i;

    Max = Kadane(a,N,a[0]);

    /*Display*/
    printf("Array [0-%d]: { ",N-1);
    for (i = 0; i<N ; i++)
            printf("%d ",a[i]);
    printf("} \n\n");
    printf("Max Sum: %d, Start Index: %d End Index: %d \n",Max,GS,GE);

    return 0;
}

[3] Iterative Method:

/*
Variable Defination
N = Number of Total Element
a[] = array
S = Starting Index
E = End Index
CMax = Current Maxumum Sum
CSI = Current Start Index
CEI = Current End Index
Max = Final Maximum Number
Ref: http://alexeigor.wikidot.com/kadane
*/
#include<stdio.h>
#include<limits.h>


int main(){
   int a[] = {-2,-1,-3,4,-1,2,1,-5,-4};

   int N=9,i;

   int Max=1<<31,S=0,E=0;

   int Cmax=0,CSI=0;
   int CEI;


   printf("Array: { ");
   for (i = 0; i<N ; i++)
            printf("%d ",a[i]);
   printf("} \n\n");



   for(CEI = 0; CEI < N; CEI++){
     Cmax = Cmax + a[CEI];
     if( Cmax > Max){
        Max = Cmax;
        E = CEI;
        S = CSI;
      }
      if( Cmax < 0 ){
         Cmax = 0;
         CSI = CEI + 1;
      }
    }

    printf("%d %d-%d\n",Max,S,E);

   return 0;
}

[4] My Designed Algorithm for 1D array O(N)[Nice to Play with it]:

[S = 0 , E = N-1]
1. Remove starting and End Minus value (SET S and E)
2. if all are positve then sum = ADD(all Element) break
3. if all are negative then sum = MAX(all Element) break
4. For i = S to E begin
5.     sum = 0;
6.     if a[i] < 0 then a[i] = sum + a[i],sum = 0;
7.     else sum = sum+a[i];
8. end
9. to be continue from 1 to 8 untile S > E
10. Return sum;


Example-1:
----------

{-2,1,-1,1,1,-1,2,1,-5}; -- > S = 0 , E =8

{-2,1,-1,1,1,-1,2,1,-5}; -- > S = 1, E = 7

{-2,0,(1+-1),0,0,(-1+1+1),0,(2+1),-5}
{-2,0,0,0,0,1,0,3,-5}  --- > S = 3, E = 7

sum = Add (a, 3, 7) = 4


Example - 2:
==============
{-2,1,-2,1,1,-1,2,1,-5};-- > S = 0 , E =8

{-2,1,-2,1,1,-1,2,1,-5};-- > S = 1 , E =7

{-2,0,(-2+1),0,0,(-1+1+1),0,(2+1),-5};-- > S = 3 , E =7
{-2,0,-1,0,0,1,0,3,-5};-- > S = 3 , E =7
{-2,0,-1,0,0,1,0,3,-5};-- > S = 4 , E =7

sum = ADD (a,4,7) = 4


Example - 3
============
{-2,1,-3,4,-1,2,1,-5,-4}; --  > S =0 E =8

{-2,1,-3,4,-1,2,1,-5,-4}; -- > S =1 E =6

{-2,0,-2,0,3,0,3,-5,-4}; -- > S =3 E =6

{-2,0,-2,0,3,0,3,-5,-4}; -- > S =4 E =6

sum = ADD (a,4,6) = 6

#include<stdio.h>

int max(int *a,int s,int e){
    int m = a[s];
    int i;
    for (i=s+1;i<=e;i++)
        if (m<a[i]) m = a[i];

    return m;
}

int ADD(int *a,int s,int e){
    int sm = 0,i;
    for (i=s;i<=e;i++) sm+=a[i];

    return sm;
}

int main(){
   int a[] = {-2,1,-3,4,-1,2,1,-5,-4};


   int N=9;
   int i,sum,flag;

   int S = 0, E = N-1,PS = 0,PE =0;

   while (S<E){
          /*Eliminate starting minus value*/
          i = S;
          PS = S;
          while(a[i]<0&&i<=E) i = i+1;
          S = i;

          printf("S: %d\n",S);
          if (S>E){ sum = max(a,PS,E); break;}



          /*Eliminate End minus value*/
          i= E;
          PE = E;
          while(a[i]<0 && i>S) i = i-1;
          E = i;
          printf("E: %d\n",E);

          if(S == PS && E == PE){ sum = ADD(a,S,PE); break;}


          /*Process*/
          sum = 0;
          flag = 0;
          for (i = S; i<=E; i++){
             if (a[i]<0){
                   a[i] = sum+a[i];
                   sum = 0;
                   if (flag ==0){S = i;flag = 1;}
             }
             else{
                sum = sum + a[i];
                a[i] = 0;
             }
          }

          if (flag == 0)/*All are positive value*/
               S = i;
          a[E] = sum;

          printf("S: %d\n",S);

          for (i = 0; i<N ; i++)
            printf("%d ",a[i]);
          printf("\n\n");
   }

   printf("Sum: %d",sum);
   return 0;
}

[5] Kadane's 2D algorithm O(N3)

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main( void )
{
    int N;
    int t = 0;
    int a[100][100];
    int pr[100];
    int S = 1<<31, s = 0, k, l, x1 = 0,x2 = 0,y1 = 0,y2 = 0,j;
 
    cin >> N;
 
    for( int i = 0; i < N; i++)
        for( j = 0; j < N; j++)
            cin >> a[i][j];
 
    for( int z = 0; z < N; z++)
    {
        for(int i = 0; i < N; i++) pr[i] = 0;
 
        for(int x = z; x < N; x++)
        {
            t = 0;
            s = 1<<31;
            j = 0;
            k = 0; l = 0;
            for(int i = 0; i < N; i++)
            {
                pr[i] = pr[i] + a[x][i];
                t = t + pr[i];
                if( t > s)
                {
                    s = t;
                    k = i;
                    l = j;
                }
                if( t < 0 )
                {
                    t = 0;
                    j = i + 1;
                }
            }
            if( s > S)
            {
                S = s;
                x1 = x;
                y1 = k;
                x2 = z;
                y2 = l;
            }
        }
    }
 
    cout << x1 << " " << y1 << " " << x2 << " "  << y2 << endl;
    cout << S;
 
    return 0;
}

Ref: http://alexeigor.wikidot.com/kadane