牛客对应题目链接：连续子数组最大和_牛客题霸_牛客网 (nowcoder.com)
一、分析题目
简单线性 dp。
1、状态表示
dp[i] 表示：以 i 位置为结尾的所有子数组中，最大和是多少。
2、状态转移方程
dp[i] = max(dp[i - 1] + arr[i], arr[i])
3、返回值
返回 dp 表里的最大值。
二、代码
1、看题解之前AC的代码
#include <iostream> using namespace std; const int N=2e5+10; int a[N], dp[N]; int main() { int n; cin >> n; for(int i=0; i<n; i++) cin >> a[i]; int res=-101; for(int i=1; i<=n; i++) { dp[i]=max(dp[i-1]+a[i-1], a[i-1]); res=max(res, dp[i]); } cout << res << endl; return 0; }
2、值得学习的代码
#include <iostream> using namespace std; const int N = 2e5 + 10; int n; int dp[N]; int arr[N]; int main() { cin >> n; for(int i = 1; i <= n; i++) cin >> arr[i]; int ret = -101; for(int i = 1; i <= n; i++) { dp[i] = max(dp[i - 1], 0) + arr[i]; ret = max(ret, dp[i]); } cout << ret << endl; return 0; }
三、反思与改进
这道题的思路正确，但还是没能通过全部测试样例。这里其实并不需要去判断当前值是正数还是负数，直接与以 i-1 位置为结尾的所有子数组中的最大和进行相加，再和当前值作比较即可。注意，这里需要的是连续子数组的最大和，重点是连续，所以如果前面的值太小就应该舍弃，从当前值开始重新累加。
