动态规划--求数列的最大字段和

我就是我 2022-03-30 13:18 223阅读 0赞

【问题描述】

N个整数，需要从中找出连续的一段数串，使得这串数的和最大。

例如-2,11，-4,13，-5，-2, 最大的子串为11，-4,13。

则最大字段和为11-4+13=20

【解析】

对于这种问题我们可以想到的方法有很多，比如蛮力法、二分法以及动态规划，相比其它前面2种方法，动态规划来解决这类问题相对于来说更方便，比如说用二分法来解决这个问题，那么我们需要分三大块去解决这个问题如下

>首先我们需要考虑这个最大字段和是在左边、右边该是这个数列的中间，这样一来我们就要从这三方面去解决，问题看似是解决了，但是效率不太高，接下来我们来介绍下动态规划来解决这个问题。

【动态规划】

>基本思想

把求解的问题分成许多阶段或多个子问题，然后按顺序求解各个子问题。换句话说，动态规划是通过**拆分问题，**定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

>基本步骤

(1)划分阶段

按照问题的时间或空间特性，吧问题划分为若干个阶段

(2)选择状态

将问题发展到各个阶段时所出现的各种情况用不同的状态表示出来

(3)确定决策并写出状态转移方程

以上就是动态规划求解的基本流程，现在我们切入主题，如何使用动态规划解决上述问题，首先请看代码

#include<iostream>
    using namespace std;
    
    int MaxSubsequenceSum(int a[],int n){
    	int temp = 0;
    	int maxsum = 0;
    	for(int i=0;i<n;i++){
    		temp = (temp + a[i]) > a[i] ?  (temp + a[i]) : a[i];//两两依次作比较，比较当前值与前面累加值 
    		if(temp > maxsum){//保留最大和 
    			maxsum = temp;
    		}
    	}
    	return maxsum;
    	
    }
    int main(){
    	int n;
    	cout << "请输入n的值:";
    	cin >> n;
    	int a[n];
    	cout << "请依次输入元素:";
    	for(int i=0;i<n;i++){
    		cin >> a[i];
    	}
    	cout << "最大字段和为:" << MaxSubsequenceSum(a,n); 
    }

>在代码中我们定义了2个变量temp和maxsum(保存最大值),其次是使用了三目运算符如下

temp = (temp + a\[i\]) > a\[i\] ?  (temp + a\[i\]) : a\[i\];

这段代码的意思是当我们通过for循环来遍历的时候，当输入的第一个数与temp相加来比较a\[i\]的值，如果temp+a\[i\] > a\[i\}那么我们将temp = temp+a\[i\]；

接下来当 i=1时按照上面的步骤依次执行下去，找到一个最大值便保存到maxsum中如下代码

if(temp > maxsum)\{//保留最大和   
            maxsum = temp;  
        \}

【运行结果】

![20190106114751761.png][]

[20190106114751761.png]: /images/20220330/23c5983a86c64a779fcfbb685f521bb4.png