算法设计与分析——动态规划——最大字段和问题

Love The Way You Lie 2022-10-08 00:56 153阅读 0赞

动态规划解决问题是自底向上。原问题的规模是n个元  
素。这n个元素不好考虑，我们先考虑n-1个元素，这样还不好考  
虑，我们考虑n-2个元素，这样依次递减，最后问题规模变成一个  
元素。但是我们发现，在递减的过程中间，子问题的最优解包含  
在原问题的最优解之中，而且子问题的解还有一些是重复的。  
因此，使用动态规划来解决这个问题。

思想：  
对字段序列进行一个循环，  
如果之前的序列b>0，则加入这个新的序列之中；  
如果之前的序列b<=0,则重新设置字段的序列和为nums\[i\]；  
如果之前的序列加上nums\[i\],的值大于之前的最大序列和，则更新最大序列和；  
我们要写出一个递归方程。我们设置一个数组b来存放最优解，首先将b\[1\]=a\[1\]，a存放的是我们的n个元素。第i个元素，他的状态就是将他放不放到数组b中（和之前的有些像）。因此，递归方程就是:b\[i\]=max\{b\[i-1\]+a\[i\],a\[i\]\}

#include<iostream>
    using namespace std;
    
    long long MaxSum(long long *nums,int n)
    {
        
    	long long sum=0;
    	long long  b=0;//b是临时的字段和的数值 
    	for(int i=0;i<n;i++)
    	{
        
    		if(b>0)
    		{
        
    			b=b+nums[i];
    		}
    		else
    		{
        
    			b=nums[i];
    		}
    		
    		if(b>sum)//更新字段和值 
    		{
        
    			sum=b;
    		}
    	}
    	
    	return sum;
    }
    int main()
    {
        
    	cout<<"请输入字段的长度：";
    	 
    		long long  n;
    	cin>>n;
    
    	long long nums[n];
    	cout<<"请输入字段序列(中间用空格隔开)：";
    	 
    	for(int i=0;i<n;i++)
    	{
        
    		cin>>nums[i];
    	} 
    	cout<<"最大字段和为："<<MaxSum(nums,n);
    	return 0;
    }

![在这里插入图片描述][20210619141014643.png]

[20210619141014643.png]: /images/20221005/1ab8168108d14b28ac1277a27c351665.png