Skip to content

Instantly share code, notes, and snippets.

@tchomphoochan

tchomphoochan/intro-dp-exmp3.cpp

Last active January 28, 2019 13:07
Show Gist options
  • Save tchomphoochan/ea355c6c4a7212270b4c66e4600d4a7e to your computer and use it in GitHub Desktop.
Save tchomphoochan/ea355c6c4a7212270b4c66e4600d4a7e to your computer and use it in GitHub Desktop.
Download ZIP
Raw
intro-dp-exmp3.cpp
int A[MAX_N];
int dp[MAX_N]; // dp[0] = 0
int ans = -1e9;
for (int i = 1; i <= n; ++i) {
dp[i] = max(A[i], dp[i-1]+A[i]);
ans = max(ans, dp[i]);
}
cout << ans << endl;
// if A[1..n] = [-2, 3, 2, -1, 4, -9, 3]
// cout << ans << endl;
// result = 8
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment