问题 A: 最大子段和
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
Geobiyye是一个喜欢思考问题的女孩子。
Geobiyye给了你一个序列，她想求出这个序列的最大子段和。
Geobiyye觉得这个问题太简单了，她将问题扩大了一倍。于是现在问题变成了：从这个序列中选出不相交的两个连续段，要求它们的和最大。
换句话说，对于给定的长度为n的序列ai，你需要给出 A,B,C,D，满足1≤A≤B≤C≤D≤n ，并且最大化下列式子：
现在Geobiyye不会这道题了，于是她将问题抛给了你。
输入
第一行一个正整数n，表示序列长度。
接下来一行n个整数a1,a2,a3,…,an，表示题目描述中的序列。
输出
一行一个整数表示最大值。
样例输入 Copy
7
2 -4 3 -1 2 -4 3
样例输出 Copy
7
提示
选择的两个区间分别为[3,5]和[7,7]。
【数据范围】
对于30%的数据：n≤100 。
对于60%的数据：n≤1000 。
对于100%的数据：n≤105,|ai|≤109 。
题目大意：给你一个序列，求出这个序列中两个互不相交的子序列的和的最大值。
思路：
由于找两个互不相交的子序列，我们可以从左到右，再从右到左分别求出这个序列的dp（）值，然后在这些dp（）值互不重叠的情况下分别找出两个dp（）的最大值相加即可。具体实现呢，可以简化这个思想，只需找出一个dp（）值就可以，我们找出正序的dp（）数组，对于逆序的情况呢，用一层for循环，每一次循环，我们用一个变量temp来存放从i到n的这些子序列中的最大子段和，然后和1到i的最大子段和相加，这样经历n次循环之后我们就找到了所要求的值。
#include <cstdio>
#include <cstring>
#include <iostream>
#define INF -999999999
using namespace std;
int ans[50050],dp[50050];
int main()
{
int t,n,i;
memset(dp,0,sizeof(dp));
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&ans[i]);
for(i=1;i<=n;i++)
dp[i]=max(dp[i-1]+ans[i],ans[i]);//从前往后找到最大
int temp=0;
int solve=INF,nmax=INF;
for(i=n;i>1;i--)//从后往前
{
temp=max(temp+ans[i],ans[i]);
nmax=max(nmax,temp);
if(solve<nmax+dp[i-1])
solve=nmax+dp[i-1];//这个就是不想交 中间隔开一个就是了前面的就是原本求得，后面一段就是上面求得。
}
printf("%d\n",solve);
return 0;
}
京公网安备 11010502036488号