• 热门专题

最大连续和,最大子矩阵和小结

作者:弱...菜  发布日期:2013-12-09 22:10:25
Tag标签:最大  连续  最大  
  • 动态规划的经典题型:

    1.最大连续和

    2.最大子矩阵和

    最后几个例题:hdu1003 模板题

    poj1050=hdu1081

    最大连续和:

    最大连续和指的是对于一个一维数组,我们要求出其中 i 到 j 个连续的元素和最大,如(6,-1,5,4,-7),最大连续和为14,是第1个到第4个元素之和,那么对于这样一个问题,我们可以这样处理:

    设 ans 为最后的最大和,初始化为负无穷大,x,y为我们ans最大的时候的区间(有的题目中不要用到),初始化都为1,flag用来指示寻找最大和区间的左端点,初始化为1,sum表示寻找过程中的中间值,初始化为0,那么我们从数组第一位开始

    sum += a[i]; 那么如果 sum>ans ,就可以把ans更新为sum,并且区间更新 x = flag, y = i ; 这里之所以要对x更新,是因为,对于sum>ans判断之后,我们应该还有一个判断,如果sum<0; 那么我们的sum更新为 0,此时flag 更新为i+1,为什么要这样呢?如果当前的 i 点之后还出现有一个区间的sum > ans,那么 我们的区间x就可以靠flag,更新啦 , 下面是模板:

     

    for(i=0;i<N;i++)
        scanf("%d",&a[i]);
    
    int x = 1,y = 1;
    int flag = 1;
    int sum = 0;
    int ans = -INF;
    for(int i = 1;i <= N;i ++)
    {
    	sum += a[i];
    	if(sum > ans)
    	{
    		ans = sum;
    		x = flag;
    		y = i;
    	}
    	if(sum < 0)//这里 不能是else 要考虑所有数为负数
    	{
    		sum = 0;flag = i+1;
    	}
    }
    最大子矩阵和:

     

    对于一维数组的连续和比较简单,那么对于一个二维的矩阵,怎么样求解其中一块小的子矩阵的最大和呢?

    其实对于二维数组,我们只要把它转化为一维数组就可以啦,那么怎么转化,结合代码理解:

     

    int temp[MAX],map[MAX][MAX];
    int getsum()
    {
    	int sum = 0,max = -INF;
    	for(int i = 1;i <= M; i ++)
    	{
    		sum += temp[i];
    		if(sum > max) max = sum;
    		if(sum < 0) sum = 0;
    	}
    	return max;
    }
    int main()
    {
    	for(int i = 1;i <= N; i ++)
    		for(int j = 1;j <= M; j ++)
    			scanf("%d",&map[i][j]);
    
    	int ans = -INF;
    	for(int i = 1; i <= N; i ++)//从第i行开始
    	{
    		memset(temp,0,sizeof(temp));
    		for(int j = i; j <= N; j ++)//从i行到N行都尝试叠加上去
    		{
    			for(int k = 1; k <= M; k ++)//把i到j行的每一列加起来。。。就是矩阵压缩
    				temp[k] += map[j][k];
    
    			int pre = getsum();//计算压缩的一维连续区间最大和
    			if(ans < pre)
    				ans = pre;
    		}
    	}
    	return 0;
    }

     

    对于一个N*M的矩阵,我们对于每一行进行所谓的矩阵压缩,就是对于第 i 行,借助一个temp数组,我们用一个for循环,把第i 到 N 行都叠加到这个一维数组上(矩阵压缩),每次叠加一行,就对这个temp求一次区间最大,那么,整个程序完了之后,我们的ans就得到啦

    最后 附上几个例题 ,后面做了再贴代码

    最大连续和:hdu1003 模板题

     

    #include <stdio.h>
    
    int main()
    {
    	int T;
    	int N,num;
    	int ans,sum,flag,x,y;
    	scanf("%d",&T);
    	for(int cas = 1; cas <= T; cas ++)
    	{
    		scanf("%d",&N);
    		ans = -1001;//这里的最小是-1000
    		sum = 0;
    		x = y = 1;
    		flag = 1;
    		for(int i = 1; i <= N; i ++)
    		{
    			scanf("%d",&num); //这里也可以在每个案例下 先输入N个数,这里 就sum += a[i];
    			sum += num;
    			if(sum > ans)
    			{
    				ans = sum;
    				x = flag;
    				y = i;
    			}
    			if(sum < 0)
    			{
    				sum = 0;
    				flag = i+1;
    			}
    		}
    		printf("Case %d:
    %d %d %d
    ",cas,ans,x,y);
    		if(cas != T) printf("
    ");
    	}
    	return 0;
    }


     

    最大子矩阵和:poj1050=hdu1081

     

    #include<stdio.h>
    #include<string.h>
    
    int N;
    int map[101][101];
    int temp[101];
    
    void Input()
    {
    	for(int i = 1;i <= N;i ++)
    		for(int j = 1;j <= N;j ++)
    			scanf("%d",&map[i][j]);
    }
    
    int getsum()
    {
    	int sum = 0,max = 0;//不用初始为-127,可以一个数也不加
    	for(int i = 1;i <= N;i ++)
    	{
    		sum += temp[i];
    		if(sum > max) max = sum;
    		if(sum < 0) sum = 0;
    	}
    	return max;
    }
    
    void dp()
    {
    	int ans = -127;
    	for(int i = 1;i <= N;i ++)//从第i行开始
    	{
    		memset(temp,0,sizeof(temp));
    		for(int j = i;j <= N;j ++)//从i行到j行都尝试一次
    		{
    			for(int k = 1;k <= N;k ++)//把i到j行的每一列加起来。。。就是矩阵压缩
    				temp[k] += map[j][k];
    
    			int pre = getsum();//计算压缩的最大和
    			if(ans < pre)//注意范围-127.。
    				ans = pre;
    		}
    	}
    	printf("%d
    ",ans);
    }
    
    int main()
    {
    	while(~scanf("%d",&N))//注意hdu1081是多案例
    	{
    	 Input();
    	 dp();
    	}
    	return 0;
    }

    个人愚昧观点,欢迎指正与讨论

     


     

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规