Skip to content

Instantly share code, notes, and snippets.

@ygabo
Created June 13, 2013 10:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ygabo/5772816 to your computer and use it in GitHub Desktop.
Save ygabo/5772816 to your computer and use it in GitHub Desktop.
Largest sum sequence
#include <vector>
#include <iostream>
using namespace std;
void main(){
int x[] = { 1, -4 ,4 ,3 , -2 ,-3, 2 ,1 };
vector<int> s(begin(x), end(x));
int max_so_far = 0, begin_so_far =0, max = 0, begin = 0, end =0;
int temp;
for(int i = 0; i < s.size(); ++i){
max_so_far += s[i];
if( max_so_far < 0 ){
begin_so_far = i+1;
max_so_far = 0;
}
else{
if( max_so_far >= max ){
max = max_so_far;
begin = begin_so_far;
end = i;
}
}
}
cout << max << endl;
cout << begin << " " << end << endl;
cin.get();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment