【动态规划】求最大子段和系列问题

知识点

---

一 . 求最大子段和

例题： 洛谷 P1115 最大子段和

题目描述

给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 n。

第二行有 n 个整数，第 i 个整数表示序列的第 i 个数字 ​。

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1

7
2 -4 3 -1 2 -4 3

输出 #1

4

说明/提示

样例 1 解释

选取 [3, 5]子段 ，其和为 4。

数据规模与约定

• 对于40% 的数据，保证 。
• 对于 100% 的数据，保证 ，。

 方法一：贪心+前缀和

#include 
#include 
#include 
#include 
using namespace std;
const int maxn=1e8+9;
int a[maxn];
int n;
int main()
{
	long long int maxx=-0x7ffffff,ans=0;
	cin>>n;
	for(int i=0;i
	{
		cin>>a[i];
		ans+=a[i]; //前面i个数字相加的和进行比较与记录
		if(ans>maxx) maxx=ans;
		if(ans<0) ans=0;
	}
	cout<
	return 0;
}

方法二：线性动态规划

#include 
#include 
#include 
#include 
using namespace std;
const int maxn=1e8+9;
long long int a[maxn],Max=-0x3f3f3f3f;
long long int dp[maxn];
int n;
int main()
{
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>a[i];
	}
	dp[0]=0;
	for(int i=1;i<=n;++i)
	{
	    dp[i]=max(dp[i-1]+a[i],a[i]);
         //在i位置的情况可以分为：继承前面的所有数的总和+当前节点的和 或 仅选择当前节点
	    Max=max(Max,dp[i]);
	}
	cout<
	return 0;
}

 

---

二 . 求双子序列最大和

例题： 洛谷 P2642 双子序列最大和

题目描述

给定一个长度为n的整数序列，要求从中选出两个连续子序列，使得这两个连续子序列的序列和之和最大，最终只需输出最大和。一个连续子序列的和为该子序列中所有数之和。每个连续子序列的最小长度为1，并且两个连续子序列之间至少间隔一个数。

输入格式

第一行是一个整数表示n。

第二行是n个整数表示整数序列。

输出格式

一个数，两个连续子序列的序列和之和。

输入输出样例

输入 #1

5
83 223 -13 1331 -935

输出 #1

1637

输入 #2

3
83 223 -13

输出 #2

70

说明/提示

对于30%的数据N<=100。

对于60%的数据有N<=10000。

对于100%的数据有N<=1000000。

数据保证运算过程不会超过long long（int64）。

 （待填坑）

#include 
#include 
#include 
#include 
#define ll long long
using namespace std;
ll int n;
const int maxn=1e7+5,INF=-2147483647;
ll int a[maxn];
ll int dp1[maxn],dp2[maxn],l[maxn],r[maxn],Max=INF;
inline ll int read()
{
	ll int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
 
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
	}
	l[0]=INF; r[n+1]=INF; //记得初始化！！！
	for(int i=1;i<=n;++i)
	{
		dp1[i]=max(dp1[i-1]+a[i],a[i]); 
		l[i]=max(l[i-1],dp1[i]);
	}
	for(int i=n;i>=1;--i)
	{
		dp2[i]=max(dp2[i+1]+a[i],a[i]);
		r[i]=max(r[i+1],dp2[i]);
	}
	
	for(int i=2;i<=n-1;++i)
	{
		Max=max(Max,l[i-1]+r[i+1]);
	}
	printf("%lld",Max);
	return 0;
}