当前位置:   article > 正文

动态规划--求数列的最大字段和_求数列的最大子段和文字描述

求数列的最大子段和文字描述

【问题描述】

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

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

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

【解析】

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

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

【动态规划】

>基本思想

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

>基本步骤

(1)划分阶段 

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

(2)选择状态

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

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

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

  1. #include<iostream>
  2. using namespace std;
  3. int MaxSubsequenceSum(int a[],int n){
  4. int temp = 0;
  5. int maxsum = 0;
  6. for(int i=0;i<n;i++){
  7. temp = (temp + a[i]) > a[i] ? (temp + a[i]) : a[i];//两两依次作比较,比较当前值与前面累加值
  8. if(temp > maxsum){//保留最大和
  9. maxsum = temp;
  10. }
  11. }
  12. return maxsum;
  13. }
  14. int main(){
  15. int n;
  16. cout << "请输入n的值:";
  17. cin >> n;
  18. int a[n];
  19. cout << "请依次输入元素:";
  20. for(int i=0;i<n;i++){
  21. cin >> a[i];
  22. }
  23. cout << "最大字段和为:" << MaxSubsequenceSum(a,n);
  24. }

>在代码中我们定义了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;
        }

【运行结果】

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小惠珠哦/article/detail/951847
推荐阅读
相关标签
  

闽ICP备14008679号