Sunday, January 15, 2012

Linear solution of Maximum subarray problem

Maximum subarray problem
Find the contiguous subarray within a one-dimensional array of numbers (containing both positive and negative numbers) which has the largest sum.

#include
using namespace std;
int main()
{
int a[] = {-2,1,-3,4,-1,2,1,-5,4};
int j =0;
int sum = 0, max = 0, str,end,next;
while(j<9) { sum += a[j]; if(sum<0) { sum = 0; next = j+1; } if(sum>max)
{
str = next;
end = j;
max = sum;
}
++j;
}
cout<
cout<<<", "<<
return 0;
}

No comments: