PAT Advanced 1007 Maximum Subsequence Sum（最大连续子列和，DP）_综合

链接：PAT Advanced 1007

Given a sequence of K integers { N_?1?? , N?₂?? , …, N?_K?? }. A continuous subsequence is defined to be { N?_i?? , N?_i+1?? , …, N?_j?? } where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤10000). The second line contains K numbers, separated by a space.

Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:

10
-10 1 2 3 4 -5 -23 3 7 -21

Sample Output:

10 1 4

题意：

给一个数字序列a₁,a₂, … ,a_n，求 i , j ( 1 ≤ i ≤ j ≤ n)，使得 a_i + … + a_j 最大，输出最大和及其a_i , a_j。

如果有多种方案使得和最大，那么输出其中i , j 最小的一组；
如果所有数都小于0，那么认为最大和为0，并输出首尾元素。

分析：

首先是最大连续子列和问题的状态转移方程：
$dp[i]=max\left \{a[i],a[i]+dp[i-1] \right \}$

dp[i]：代表以a[i]结尾的连续子序列的最大和
所以a[i]必选，然后判断是否要选择dp[i-1]（很明显当dp[i-1]为负时前面的都可以剪去）

最后dp数组中最大的值即为最大连续子列和。

题目还要求输出a_i , a_j：

若dp[k]为答案，由于dp[k]的结尾元素一定是a[k]，那么a_j=a[k]；但是dp[k]对应序列的首元素并不确定，所以利用数组s[i]来记录dp[i]对应序列的首元素。

若a[i] ≥ a[i] + dp[i-1]，则s[i] = s[i-1]；
若a[i] < a[i] + dp[i-1]，则s[i] = a[i]

以下代码：

#include<cstdio> 
using namespace std;
const int INF=1e9;
const int maxn=10010;
int main()
{
    	int K,a[maxn];scanf("%d",&K);for(int i=0;i<K;i++)scanf("%d",&a[i]);int ans,dp[maxn],s[maxn],first,last;ans=dp[0]=s[0]=first=last=a[0];      //都初始化为a[0]for(int i=1;i<K;i++){
    if(a[i]+dp[i-1]>=a[i]){
    dp[i]=a[i]+dp[i-1];s[i]=s[i-1];}else{
    dp[i]=a[i];s[i]=a[i];}if(dp[i]>ans)            //ans对应最大dp[i]{
               			 //为符合题目要求，不能用 >=ans=dp[i];first=s[i];last=a[i];}}if(ans>=0)printf("%d %d %d",ans,first,last);elseprintf("0 %d %d",a[0],a[K-1]);return 0;
}