1007 Maximum Subsequence Sum (25分)
1007.png
分析：
本题要求最大连续子序列的和，输出最大之和以及子序列第一个数和最后一个数。如果方案不唯一，则输出i，j最小的一组。如果所有数都是负数，则最大和为0，然后输出首尾元素。
先考虑如何求最大和。以dp[i]表示以A[i]作为末尾的连续序列最大和。以本题为样例dp[0]=-10,dp[1]=1,dp[2]=3......容易知状态转移方程为dp[i]=max{A[i],dp[i-1]+A[i]}。通过遍历就可通过dp[0]把所有dp求出来，最大和就是dp数组中最大的数。
再考虑如何求最大连续子序列的首位元素，以s[i]表示以A[i]作为结尾的最大连续子序列是从哪个元素开始，根据状态转移方程易知s[i]=i或者s[i]=s[i-1]。
在一开始的时候先考虑所有数是负数的情况，节省时间。
C++:
#include <cstdio>
const int maxn = 10010;
int arr[maxn], dp[maxn], s[maxn];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
//先处理全为负数的情况
bool flag = false; //是否有正数
for (int i = 0; i < n; i++) {
if (arr[i] >= 0) {
flag = true;
break;
}
}
if (flag == false) {
printf("0 %d %d\n", arr[0], arr[n - 1]);
return 0;
}
dp[0] = arr[0];
s[0] = 0;
for (int i = 1; i < n; i++) {
if (dp[i - 1] + arr[i] > arr[i]) {
dp[i] = dp[i - 1] + arr[i];
s[i] = s[i - 1];
} else {
dp[i] = arr[i];
s[i] = i;
}
}
int index = 0;//dp数组最大值的下标
for (int i = 1; i < n; i++) {
if (dp[i] > dp[index]) {
index = i;
}
}
printf("%d %d %d\n", dp[index], arr[s[index]], arr[index]);
return 0;
}
