题解 | #最大子串和#
最大子串和
https://ac.nowcoder.com/acm/problem/235948
从某一个数字来看，它的最大连续子串和是前面一个数字的最大连续子串和加上它本身，和他本身取较大的那一个。当位于第一个的时候自然就是他自身所以可以实现一个动态规划。
故递推式：dp[i] = max(dp[i-1]+dp[i], dp[i])。
//dp[i] = max(dp[i-1]+dp[i], dp[i])
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6+10;
int n;
int a[maxn];
int dp[maxn];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for (int i=1;i<=n;i++) {
cin>>a[i];
}
int ans = 0;
for (int i=1;i<=n;i++) {
dp[i] = max(dp[i-1]+a[i], dp[i]);
ans = max(ans, dp[i]);
}
cout<<ans;
return 0;
}
