动态规划最大子数组和到最大子矩阵

in 编程
关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9
  1. 定义


    • 大问题可以分成若干个独立的小问题叫做动态规划。
    • 大问题可以分成若干个需要重复计算的问题叫做分治。
  2. 拓展


    动态规划可以是单向,可以是横纵结合。

    • 单向:最大子数组问题
    • 结合:最大子矩阵问题
  3. 最大子数组问题


    • 假设m-n的和最大,则有max = rangesum(m,n),且有,rangesum(0-m)<0,range(n,len)<0

    现实生活中,就是买股票,在最低价的时候买入,在最高价格的时候抛出,形成利益最大化。


    	int MaxSum(int n,int *a)
    	{
    		int sum=a[0],presum=0;
    		for(int i=0; i<n; i++)
    		{
    			if(presum>0)
    			{
    				presum+=a[i]; //对于前面的和大于0,说明是仍处于盈利状态
    			}
    			else
    			{
    				presum=a[i]; // 如果小于0,说明出现了亏损。那么这个时候及时止损。
    			}
    			if(presum>sum)
    			{
    				sum = presum; //0-i出现的最大sum,也就是出现的总体增。
    			}
    		}
    		return sum;
    	}
    

    • sum记录最优解

    • presum继续做试探求解。

  4. 最大子矩阵


    	#include<stdio.h>
    	#define N 102
    	int map[N][N]={0};
    
    	int getMax(int (*a)[N],int n,int (*b)[N])
    	{
    		int i,sum=a[0][1]-b[0][1],t=0;
    		for(i=1;i<=n;i++)
    		{
    			if(t>0)
    			{
    				t+=(*a)[i]-(*b)[i];
    			}
    			else
    			{
    				t=(*a)[i]-(*b)[i];
    			}
    			sum=t>sum?t:sum;
    		}
    		return sum;
    	}
    
    	int main()
    	{
    		int m,n,p,i,j,k,max;
    		scanf("%d%d",&m,&n);
    		for(i=1;i<=m;i++)
    		{
    			for(j=1;j<=n;j++)
    			{
    				scanf("%d",&map[i][j]);
    				map[i][j]+=map[i-1][j];
    				//数组树的方式存储,任意两个节点的差是这两个节点之间的和。方便后续运算。
    			}
    		}
    
    		max = map[1][1];
    		for(i=1;i<=m;i++)
    		{
    			for(j=i;j<=m;j++)
    			{
    				k=getMax((int (*)[102])map[j],n,(int (*)[102])map[i-1]);
    				// 同样的动态规划策略,求解 从 i行到j行的 最大子矩阵和。
    				// 多了一层j循环,也就是多了一个纵向的变化 横向 a[i] 值。
    				// 用了同样的策略。
    				// 动态规划主要是问题分析,拆分,关联。
    				// 求解 高度为 j-i (j-i的和) 的 最大子数组和 。
    				max=max>k?max:k;
    			}
    		}
    		printf("%d\n",max);
    		return 0;
    	}
    
关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9
扫一扫关注公众号添加购物返利助手,领红包
Comments are closed.

推荐使用阿里云服务器

超多优惠券

服务器最低一折,一年不到100!

朕已阅去看看