动态规划求最大字段和

提示：这里可以添加系列文章的所有文章的目录，目录需要自己手动添加
例如：第一章 Python 机器学习入门之pandas的使用

---

提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档

---

动态规划

1.要素

动态规划两大要素：最优子结构、重叠子问题
最优子结构：当问题的最优解包含了其子问题的最优解时，该问题具有最优子结构性质
重叠子问题：在用递归算法自底向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算，具有子问题重叠性质。这类问题称重叠子问题

2.基本思想

将待求解问题分解成若干个子问题，先求解子问题，然后结合这些子问题的解得到原问题的解。求解的问题经分解得到的子问题往往不是相互独立的

3.适用于解最优化问题步骤

1）找出最优解的性质，并刻画其结果特征（分析最优解结构）
2）递归地定义最优解（建立递归关系）
3）以自底向上的方法计算得到的信息，构造最优解（计算最优解）
4）根据计算最优值得到的信息，构造最优解（构造最优解）
1）2）3）为基本步骤

一、最大字段和问题

给定由n个正数（可能为负整数）组成的序列a1,a2,…,an,求该序列形如的子段和的最大值，当所有整数均为负整数时定义其最大字段和为0.

二、使用步骤

给出一段序列，选出其中连续且非空的一段使得这段和最大。找最大字段的和。
如果说序列中所有的数都是正数，那么最大子段和一定是所有数的和

1.引入库

代码如下（示例）：

// 实验2.1最大字段和问题.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
 
#include <iostream>
using namespace std;
 
//最大字段和：蛮力法
int MaxSum_Manli(int a[], int n){
 
	int sum, maxSum;
	sum = 0;
	maxSum = 0;
	int i, j, k;
	for (i = 0; i < n; i++)	{
		for (j = i; j < n; j++){
			sum = 0;
			for (k = i; k <= j; k++)
				sum += a[k];
			if (sum > maxSum)
				maxSum = sum;
		}
	}
	return maxSum;
}
 
//最大字段和：分治法实现
int MaxSum_Fenzhi(int a[], int left, int right) {
	int sum = 0, midSum = 0, leftSum = 0, rightSum = 0, i, j;
	int center, s1, s2, lefts, rights;
	if (left == right)                      //如果序列长度为1，直接求解
		sum = a[left];
	else {
		center = (left + right) / 2;             //划分
		leftSum = MaxSum_Fenzhi(a, left, center);          //对应情况①，递归求解
		rightSum = MaxSum_Fenzhi(a, center + 1, right);      //对应情况②，递归求解
		s1 = 0; lefts = 0;                         //以下对应情况③，先求解s1
		for (i = center; i >= left; i--){
			lefts += a[i];
			if (lefts > s1) s1 = lefts;
		}
		s2 = 0; rights = 0;                        //再求解s2
		for (j = center + 1; j <= right; j++){
			rights += a[j];
			if (rights > s2) s2 = rights;
		}
		midSum = s1 + s2;                          //计算情况③的最大子段和
		if (midSum < leftSum) sum = leftSum;           //合并解，取较大者
		else sum = midSum;
		if (sum < rightSum) sum = rightSum;
	}
	return sum;
 
}
 
//最大字段和：动态规划法
int MaxSum_Dongtai(int a[], int n){
	int sum, maxSum;
	int i;
	sum = 0;
	maxSum = 0;
	for (i = 0; i < n; i++)	{
		sum += a[i];
		if (sum > maxSum)
			maxSum = sum;
		else if (sum < 0)
			sum = 0;
	}
	return maxSum;
}
 
int main(){
	int a[100] = { 2,11,-4,13,-5,-2,20 };
	int n = 7;
	cout << "请输入数字串个数：";
	cin >> n;
	cout << "请依次输入 " << n << " 个数字：";
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	cout << endl;
	int sum1 = MaxSum_Manli(a, n);
	int sum2 = MaxSum_Fenzhi(a, 0, n-1);
	int sum3 = MaxSum_Dongtai(a, n);
	cout << "使用蛮力法求得：" << sum1 << endl;
	cout << "使用分治法求得：" << sum2 << endl;
	cout << "使用动态规划法求得：" << sum3 << endl;
}

总结

顺序递归加字段，若字段和小于零则置为0，继续进行计算，顺次相加。
计算过程记录最大字段和并进行与当前字段和的比较。最后返回最大字段和