杭电OJ-Max Sumamp;amp;Max Sum Plus Plus（DP）

#include<iostream>//d[i]=max(d[i-1]+a[i],a[i]),a[i]要么是以第i个结尾的头，要么是以第i个结尾的尾
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int a[100001];
int dp[100001];
int main() {int t;int n;cin >> t;for (int i = 1; i <= t; i++) {cin >> n;for (int i = 0; i <= n; i++) {dp[i] = -1001;}memset(a, 0, sizeof(a));for (int i = 1; i <= n; i++) {cin >> a[i];}int start, end;int max0 = -1001;for (int i = 1; i <= n; i++) {dp[i] = max(dp[i - 1] + a[i], a[i]);if (dp[i] > max0) {max0 = dp[i];end = i;}}int sum = 0;for (int i = end; i > 0; i--) {sum += a[i];if (sum == max0)start = i;}printf("Case %d:\n", i);printf("%d %d %d\n", max0, start, end);if (i < t)printf("\n");}return 0;
}//dp[j]表示分成i组时，以第j个结尾的pair sum的最大值
#include<iostream>
#include<algorithm>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
int a[1000001];
int dp[1000001];
int Max[1000001];
int main() {int m, n,mmax;while (cin >> m >> n) {for (int i = 1; i <= n; i++) {cin >> a[i];}memset(Max, 0, sizeof(Max));memset(dp, 0, sizeof(dp));for (int i = 1; i <= m; i++) {mmax = -inf;for (int j = i; j <= n; j++) {dp[j] = max(dp[j - 1] + a[j], Max[j - 1] + a[j]);Max[j - 1] = mmax;mmax = max(mmax, dp[j]);}}cout << mmax <<endl;}return 0;
}