1

Given a length n of the one-dimensional array a, please find a sub-array in this array, so this sub-array and the sum = a [i] + a [i +1] + ... ... + a [j] the largest , where i> = 0, i <n,j> = i, j <n,

For example, 31 -41 5926-535897-93 -23 84

59 +26-53 +58 +97 submatrix = 187 was asked for the maximum sub array.

Example code:

#include <iostream> using namespace std ; // Direct brute, find out all the possible combinations and O(N^3) int getSum1(int a[],int N) { int max=-10000000; for(int i=0;i<N;i++) { for(int j=i;j<N;j++) { int tmp=0; for(int k=i;k<=j;k++) tmp+=a[k]; if(tmp>max) max=tmp; } } return max; } // With memory of recursive method O(N^2) int getSum2(int a[],int N) { int* cumarr=new int[N]; cumarr[0]=a[0]; // Pretreatment, makes the combinatorial and easier for(int i=0;i<N;i++)// Some parts and to build first { cumarr[i]=cumarr[i-1]+a[i]; } int max=-10000000; for(int i=0;i<N;i++) { for(int j=i;j<N;j++) { // Optimization of place int tmp=cumarr[j]=cumarr[i]; if(tmp>max) max=tmp; } } delete[] cumarr; return max; } // The third kind , int maxSubArray(int a[],int N) { int b=0,max=-10000000; for(int i=0;i<N;i++) { if(b>0) b+=a[i]; // Greater than 0, the previous accumulated else b=a[i]; if(b>max) max=b; } return max; } int main () { int a[]={31,-41,59,26,-53,58,97,-93,-23, 84}; int N=sizeof(a)/sizeof(a[0]); cout<<getSum1(a,N)<<endl; cout<<getSum1(a,N)<<endl; cout<<maxSubArray(a,N)<<endl; return 0 ; }

2