C++实现最大字段和

又是一道非常基础且经典的动态规划题目：假设有一个整数序列，我们将连续的几个元素组成的序列称为子段，要求我们得出所有子段和中最大的一个~

例如：{-2,11，-4,13，-5，-2}，这一序列中，最长子段和为20——也即{11，-4，13}这一段的和~

一.思想和递归方程 

DP的核心就是划分子问题和找出状态转移方程~这里很明显：我们要求的子问题就是——在没有加入当前位时最大的子段和，和加入当前位后的子段和，两者哪个大。如果前者大，则说明该元素不应该加入；反之则应该加入~

 在{-2,11，-4,13，-5，-2}：

• 对于{-2}来说，该位加上11和11本身相比较，后者更大，因此我们应该舍弃11之前的全部元素，也即最大子段的开头在当下来看应该以11为开头~
• 对于{-2,11}，此时和为9，而加入-4后变为了5，则不得不将-4加入子段和，继续寻找下规模更大的子问题中是否有更好的解~

因此我们得出状态转移方程：

DP[i]=max(DP[i-1]+V[i-1],V[i-1]); 

其中，V即为目标数组~

二.编码 

因此我们得出如下代码：

#include <iostream>
#include <cmath>
#include <vector> 
using namespace std;
void MaximumSum(vector<int> V)
{
	int DP[V.size()+1];
	for(int i=0;i<=V.size();i++)
		DP[i]=0;//必须初始化 
	for(int i=1;i<=V.size();i++)
		DP[i]=max(DP[i-1]+V[i-1],V[i-1]);
	cout<<"不同长度下最大子段和分别为："<<endl;
	for(int i=0;i<=V.size();i++)
		cout<<DP[i]<<" ";
}


int main()
{
	vector<int> V;
	int n=0,temp=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>temp;
		V.push_back(temp);
	}
	MaximumSum(V);
	return 0;
}

测试两次，是不是和你手算的一致？

三.求出最大和

细心的小伙伴发现了，这时我们的DP数组——最后一位不再是我们要求的最大值了！这时该问题和很多动态规划题不一样的一个特色。原因在于，我们求出的这些子段和可以理解为一种局部的最大值而已，换句话说子问题规模越大可能带来副作用——不像公共子序列那样必定规模越大越长。解决起来也好说，只需要找出DP中的最大值即可~

#include <iostream>
#include <cmath>
#include <vector> 
#include <string>
using namespace std;
void MaximumSum(vector<int> V)
{
	int DP[V.size()+1];
	string target="";//最大子段 
	for(int i=0;i<=V.size();i++)
		DP[i]=0;//必须初始化 
	for(int i=1;i<=V.size();i++)
		DP[i]=max(DP[i-1]+V[i-1],V[i-1]);
	cout<<"不同长度下最大子段和分别为："<<endl;
	for(int i=0;i<=V.size();i++)
		cout<<DP[i]<<" ";
	cout<<endl;
	int answer=0;
	for(int i=0;i<=V.size();i++)
		if(DP[i]>answer)
			answer=DP[i];			
	cout<<answer<<endl;

}


int main()
{
	vector<int> V;
	int n=0,temp=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>temp;
		V.push_back(temp);
	}
	MaximumSum(V);
	return 0;
}