#include <stdio.h>
#include<conio.h>
#include<iostream.h>
#include<stdlib.h>
int max_so_far = 0;
int max_ending_here = 0;
int main()/// its also O(n) solution chk out this
{
int a[]={5, 7, -3, 1, -11, 8, 12};//{-2, 1, -3, 4, -1, 2, 1, -5,
4}; O(n) Best Algo
int size=sizeof(a)/sizeof(int);
for(int i=0;i<size;i++)
{
max_ending_here = 0>max_ending_here + a[i]? 0 :
max_ending_here + a[i];//(a > b) ? a : b.
max_so_far = max_so_far>max_ending_here? max_so_far :
max_ending_here;
}
cout<< max_so_far;
getch();
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
