maximum subarray

mnnit.rahul Tue Feb 03, 2009 3:05 am

find maximum sub array in an array

eg,, 5 4 -2 -6 12 5 -1

ans = 12+5=17

$corpion Tue Feb 03, 2009 11:00 pm

i don think 17 is correct ans for this...
its 5+4-2-6+12+5=18 Rolling Eyes

Admin Wed Feb 04, 2009 12:43 am

reference:http://en.wikipedia.org/wiki/Kadane%27s_Algorithm

Code:: #include<iostream> #include<string> using namespace std; /* Kadane's Algorithm. it scans through the array, finding the maximum subarray that ends at that position Note:such a subarray can be empty also. */ int main() { int array[10] = {2, -1, -3, -4, 1, 2, -1, 5, 4,-1}; int start,end,x; start = end =0; int s=1<<31; //1<<31 is the maximum possible negative value the int can hold,an approximation of negative infinity for (int i=0 ,j=0,t=0; i<10;i++) { t=t+array[i]; if(t>s) { start=j; end=i; s=t; } if(t<0) { t=0; j=i+1; } } cout<<"sum = "<<s<<endl; for (int i=start;i<=end;i++) { cout<<array[i]<<" "; } cout<<endl; //cin>>start; }

Sponsored content

Re: maximum subarray