1007 Maximum Subsequence Sum（动态规划）

蔚落 2024-04-08 08:49 28阅读 0赞

## 1007 Maximum Subsequence Sum ##

### 0、题目 ###

Given a sequence of  K K K integers  \{ N 1 , N 2 , . . . , N K \} \\\{ N\_1, N\_2, ..., N\_K \\\} \{ N1,N2,...,NK\}. A continuous subsequence is defined to be  \{ N i , N i + 1 , . . . , N j \} \\\{ N\_i, N\_\{i+1\}, ..., N\_j\\\} \{ Ni,Ni\+1,...,Nj\} where  1 ≤ i ≤ j ≤ K 1≤i≤j≤K 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 \} \\\{ -2, 11, -4, 13, -5, -2 \\\} \{ −2,11,−4,13,−5,−2\}, its maximum subsequence is  \{ 11 , − 4 , 13 \} \\\{ 11, -4, 13 \\\} \{ 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 K K (≤10000). The second line contains  K K 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 i i and  j j j (as shown by the sample case). If all the  K K 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

### 1、大致题意 ###

找出一组数中**和最大的子数组**（数组的头和尾没有限制），并输出该子数组的和、子数组的第一个元素在原数组中的下标、子数组的最后一个元素在原数组中的下标

### 2、基本思路 ###

使用动态规划来解题，`dp[i]`保存的是到  i i i 的位置的最大的值，`pre[i]`记录子数组开始的下标。然后就是简单选与不选的问题：

*  如果选：
    
     *  `dp[i] =dp[i-1]+num[i]`
     *  `pre[i] = pre[i - 1]`，一直保持着开始选的那个位置
 *  如果不选：
    
     *  `dp[i] = num[i]`
     *  `pre[i] = i`

### 3、解题过程 ###

#### 3.1 坑点 ####

这道题的坑点其实在题目里面已经告诉我们了。

`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.`

就是上面的这句话，应该是 `测试点4`在测这个坑点

### 3.2 AC代码 ###

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=10010;
    int k,a[maxn],dp[maxn],pre[maxn];
    int maxindex,maxvalue;
    
    int main() {
        
    	scanf("%d",&k);
    	for(int i=1; i<=k; i++) {
        
    		scanf("%d",&a[i]);
    	}
    	dp[1]=a[1];
    	pre[1]=1;
    	for(int i=2; i<=k; i++) {
        
    		if(dp[i-1]+a[i]>a[i]) {
        
    			pre[i]=pre[i-1];
    			dp[i]=dp[i-1]+a[i];
    		} else {
        
    			pre[i]=i;
    			dp[i]=a[i];
    		}
    	}
    	maxindex=1;
    	maxvalue=-1;
    	for(int i=1; i<=k; i++) {
        
    		if(dp[i]>maxvalue) {
        
    			maxvalue=dp[i];
    			maxindex=i;
    		}
    	}
    	if (maxvalue==-1) {
        
    		cout<<"0"<<" "<<a[1]<<" "<<a[k];
    	} else {
        
    		cout<<maxvalue<<" "<<a[pre[maxindex]]<<" "<<a[maxindex];
    	}
    	return 0;
    }