P1115最大子段和

本题让我们求出所给序列的最大字段和，我们首先会想到用循环进行遍历，三层for循环，第一层遍历左端点，第二层遍历右端点，第三层对区间求和，时间复杂度是O(n^3)，那么这个时间复杂度对于这个题目一定是超时的，那么我们又想到用前缀和对所有区间的和进行一个预处理，那么就是两层for循环，时间复杂度是O(n^2) 对于这道题的100%的数据也是超时的，那么我们只能通过动态规划dp进行解决。

动态规划首先需要确定状态和状态方程，那么我们这道题

状态:dp[i] 代表以第i个元素为结尾的最大子段和

状态转移方程：dp[i] = max(dp[i-1]+a[i],a[i])

对于一个元素，我们可以之选自身为一个区间，也可以选择自身加上 上一个元素作为结尾的最大子段和例如 

index    1  2 3  4 5  6 7  a           2 -4 3 -1 2 -4 3 dp          2 -2 3  2 4  0 3

那么有了状态和状态转移方程我们的题目就解决一大半了

剩下就是根据题目编写代码即可

#include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 10; int a[N], dp[N]; /* 序列 单序列 1 2 3 4 5 6 7 a 2 -4 3 -1 2 -4 3 dp 2 -2 3 2 4 0 3 dp 2 -2 3 2 4 0 3 状态：dp[i] 以第i个元素为结尾的最大字段和 状态转移方程：dp[i] = max(dp[i-1]+a[i],a[i]) */ signed main() { int n; cin >> n; //边界 dp[0] = 0; int maxx = -0x3f3f3f3f;//最大值初始化为最小，注意本题有负数 ios::sync_with_stdio(false); cin.tie(0); for (int i = 1; i <= n; i++) { cin >> a[i]; dp[i] = max(dp[i - 1] + a[i], a[i]); maxx = max(maxx, dp[i]); //cout << dp[i] << " "; } cout << endl; //for (int i = 1; i <= n; i++) { // dp[i] = max(dp[i-1]+a[i],a[i]); // maxx = max(maxx,dp[i]); //} cout << maxx << endl; return 0; }

除此以外需要注意边界，是否需要手动处理，还是默认为一个值即可，对于这道题，可以默认第0个元素的dp[0] = 0。另外要注意，动态规划中所有的状态都是最优的，就是所谓的最优子结构，我们可以通过打印dp表来验证我们的代码是否是有问题的。