本文主要是介绍NYoj 104 最大和 [经典动态规划2],希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
/*NYoj 104 最大和经典动态规划2.再次写这个题是时候,差不多没有调试就A了.小有成就感.思路:子串和就相当于该问题的一个子问题.将行进行组合就可以了.
*/
#include<stdio.h>
#include<string.h>
#define max(a,b) a>b?a:b
int MAX(int a[],int n)
{int dp[105]={0};dp[1]=a[1];int Max=dp[1];for(int i=2;i<=n;i++){dp[i]=max(dp[i-1]+a[i],a[i]);Max=max(dp[i],Max);}return Max;
}
int main()
{int T;scanf("%d",&T);while(T--){int map[102][102];int r,c;scanf("%d%d",&r,&c);for(int i=1;i<=r;i++)for(int j=1;j<=c;j++)scanf("%d",&map[i][j]);int m=map[1][1];for(int i=1;i<=r;i++){for(int j=i;j<=r;j++){int list[102];for(int h=1;h<=c;h++){int sum=0;for(int k=i;k<=j;k++)sum+=map[k][h];list[h]=sum;}m=max(m,MAX(list,c));}}printf("%d\n",m);}
}
这篇关于NYoj 104 最大和 [经典动态规划2]的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!