[ create a new paste ] login | about

Link: http://codepad.org/rTNGiyWM    [ raw code | output | fork ]

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:
1
2
3
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 


Create a new paste based on this one


Comments: