1007 Maximum Subsequence Sum

Given a sequence of K integers { N1, N2, ..., 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.

给定 K 个整数的序列 { N_1, N_2, ..., N_K }，一个连续子序列被定义为 { N_i, N_{i+1}, ..., N_j }，其中 $1 \leq i \leq j \leq K$。最大子序列是元素和最大的连续子序列。例如，给定序列 { -2, 11, -4, 13, -5, -2 }，其最大子序列为 { 11, -4, 13 }，最大和为 20。

现在你需要找到最大和，以及最大子序列的第一个和最后一个数字。

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.

输入格式：

每个输入文件包含一个测试用例。每个测试用例占两行。第一行包含一个正整数 K（\leq 10000）。第二行包含 K 个数字，以空格分隔。

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.

输出格式：

对于每个测试用例，在一行中输出最大和，以及最大子序列的第一个和最后一个数字。数字必须以一个空格分隔，但行末不能有多余空格。如果最大子序列不唯一，则输出最小索引 i 和 j 的子序列（如样例所示）。如果所有 K 个数字都是负数，则其最大和定义为 0，并且你需要输出整个序列的第一个和最后一个数字。

Sample Input:

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

Sample Output:

10 1 4

我的思路

很明显是一个经典的动态规划问题

dp公式如下：

dp(i)=max(dp(i−1)+seq[i],seq[i])

力扣有详细题解：

https://leetcode.cn/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/

#include<bits/stdc++.h>
using namespace std;
int main(){
	int k;
	cin>>k;
	int seq[k];
	for(int i=0;i<k;i++){
		cin>>seq[i];
	}
    //动态规划数组
	int dp[k];
    //子序列头部记录数组
	int path[k];
    //动态规划数组初始化
	dp[0]=seq[0];
    //子序列头部数组初始化
	path[0]=0;
    //记录最大子序列尾部
	int res=0;
	for(int i=1;i<k;i++){
		if(dp[i-1]+seq[i]>=seq[i]){
			dp[i]=dp[i-1]+seq[i];
			path[i]=path[i-1];
		}
		else{
			dp[i]=seq[i];
			path[i]=i;
		}
		if(dp[res]<dp[i]){
			res=i;
		}
	}
    //如果都小于0，输出0，数组第一个值，数组最后一个值
	if(dp[res]<0)cout<<0<<" "<<seq[0]<<" "<<seq[k-1];
	else cout<<dp[res]<<" "<<seq[path[res]]<<" "<<seq[res];
}

AC

Solution

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    vector<int> v(n);
    int leftindex = 0, rightindex = n - 1, sum = -1, temp = 0, tempindex = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
        temp = temp + v[i];
        if (temp < 0) {
            temp = 0;
            tempindex = i + 1;
        } else if (temp > sum) {
            sum = temp;
            leftindex = tempindex;
            rightindex = i;
        }
    }
    if (sum < 0) sum = 0;
    printf("%d %d %d", sum, v[leftindex], v[rightindex]);
    return 0;
}