题目描述
给定一个包含 K 个整数的序列 {N1,N2,…,NK}。
连续子序列定义为 {Ni,Ni+1,…,Nj},其中 1≤i≤j≤K。
最大子序列是指序列内各元素之和最大的连续子序列。
例如,给定序列 {−2,11,−4,13,−5,−2},它的最大子序列为 {11,−4,13},其各元素之和为 20。
现在你需要求出最大子序列的各元素之和,并且输出最大子序列的第一个元素和最后一个元素的值。
输入格式
第一行包含一个整数 K。
第二行包含 K 个整数。
输出格式
输出一行三个整数,分别表示最大子序列的各元素之和以及最大子序列的第一个元素和最后一个元素的值。
设最大子序列为 {Ni,Ni+1,…,Nj},如果答案不唯一,则选择 i 更小的解,
如果仍不唯一,则选择 j 更小的解。
注意,我们规定,如果所有 K 个数字均为负数,则其最大和定义为 0,
并且应该输出整个序列的第一个数字和最后一个数字。
数据范围
1≤K≤10000,
序列内元素的绝对值不超过 105。
输入样例:
10
-10 1 2 3 4 -5 -23 3 7 -21
输出样例:
10 1 4
算法1
本题使用动态规划
我们假设和最大的连续子序列的结尾是 num[i]。 那么这个和最大的连续子序列就有两种构成可能
1 num[x],num[x+1]…num[i-1],num[i]的和 num[x],num[x+1]…num[i-1]的和+num[i] 更大 比如 序列 1,2,3, 9,是以9结尾的连续子序列 和为15
2 num[i] num[i]更大 比如 序列 -1,-2,-3, 9 和最大的连续子序列并且以9结尾就是9单个数字
情况1中 1+2+3 又可以认为是 以num[i-1]为结尾 的最大连续子序列的和 ,
如果我们定义dp[i] 是以num[i]为结尾的最大连续子序列的和 那么
上面情况1 2 可以归纳成状态方程 dp[i] = max(dp[i-1]+num[i],num[i])
这样就解决了 求和最大的连续子序列的和的问题。
连续子序列的边界L R的求得如下
因为dp[i] 表示以num[i]结尾的 和最大的连续子序列
那么右边界肯定是R =i , 左边界如果是情况1 则等于dp[i-1]的左边界 如果是情况2 那么L =i
C++ 代码
#include <iostream>
using namespace std;
const int N = 10010;
int n;
int arr[N];
struct DP{
long long val;
int l;int r;
}dp[N];
int main()
{
cin >> n;
int allneg = 1;
for(int i = 1 ;i <= n ;i++){
cin >> arr[i];
if(arr[i] >= 0) allneg=0;
}
if(allneg == 1){
cout << 0 << " " << arr[1] << " " << arr[n] << endl;
return 0;
}
dp[0].l = 1;
for(int i = 1;i <=n;i++){
dp[i].l = dp[i-1].l;
dp[i].val = max(dp[i-1].val+arr[i],(long long) arr[i]);
dp[i].r = i;
if(dp[i-1].val+arr[i] < arr[i]){ dp[i].l = i; }
}
struct DP ans = dp[1];
for(int i = 1; i <=n;i++){
if(ans.val < dp[i].val){
ans = dp[i];
}
}
cout << ans.val << " " << arr[ans.l] <<" " << arr[ans.r] << endl;
return 0;
}