Largest sum subarray

Recursion: M[i] = max sum subarray ending here

M[i] = max(M[i-1] + a[i], a[i])

Loved this code 🙂

#include<algorithm>
#include<iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  int max_sum = 0, run_sum = 0;
  for (int i = 0, t = -1; i < n; ++i) {
    cin >> t;
    run_sum = max(run_sum + t, t);
    max_sum = max(run_sum, max_sum);
  }
  cout << max_sum << endl;
  return 0;
}
Advertisements
%d bloggers like this: