mohit_at_codepad
-
C++,
pasted
on May 14:
|
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
int find_max(int *arr, int arrlen, int *start, int *count) {
struct node {
int from, to, sum;
};
node seh = {0, -1, 0};
node best = seh;
for(seh.to = 0; seh.to < arrlen; ++seh.to) {
const int newSum = seh.sum + arr[seh.to];
if(newSum > arr[seh.to]) {
seh.sum = newSum;
} else {
seh.from = seh.to;
seh.sum = arr[seh.to];
}
if(best.sum < seh.sum) best = seh;
}
*start = best.from;
*count = best.to - best.from + 1;
return best.sum;
}
int main(int c, char *const *v) {
int count = c-1;
vector<int> vi(count);
if(count < 1) {
cout << "Error: No command line arguments found" << endl;
cout << "Testing dummy data set: {4, -3, -2, 2, 3, -1, 3, -12, 5, -9, 0, -1}" << endl;
int a[] = {4, -3, -2, 2, 3, -1, 3, -12, 5, -9, 0, -1};
count = static_cast<int>( sizeof a / sizeof a[0] );
vi.insert(vi.begin(), a, a + count);
} else {
for(int i = 1; i < c; ++i) stringstream(v[i]) >> vi[i-1];
}
int *arr = &vi[0];
int st, cn;
const int s = find_max(arr, count, &st, &cn);
cout << s << ':';
for(int i= 0; i < cn; ++i) cout << arr[st+i] << ' ';
cout << endl;
return 0;
}
|
Output:
|
Error: No command line arguments found
Testing dummy data set: {4, -3, -2, 2, 3, -1, 3, -12, 5, -9, 0, -1}
7:2 3 -1 3
|
|