hdu 1081 最大子矩阵和

Love The Way You Lie 2022-08-03 11:40 132阅读 0赞

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    int maze[102][102];
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    int t;
                    scanf("%d",&t);
                    maze[i][j]=maze[i][j-1]+t; //每一行的前j列和
                }
            }
    
            int ans=-inf;
            for(int i=1;i<=n;i++)
            {
                for(int j=i;j<=n;j++)
                {
                    int sum=0;
                    for(int k=1;k<=n;k++)  //计算从第i列到第j列中最大子矩阵
                    {
                        sum+=maze[k][j]-maze[k][i-1];  
                        if(sum>ans)ans=sum;
                        if(sum<0)sum=0;
                    }
                }
            }
         
            printf("%d\n",ans);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，132人围观）

还没有评论，来说两句吧...

相关阅读

相关 java最大子矩阵

问题描述小明有一个大小为 � × � N×M 的矩阵, 可以理解为一个 � N 行 � M 列的二维数组。我们定义一个矩阵 �

男娘i/ 2024年03月26日 13:17/ 0 赞/ 41 阅读

相关最java大子矩阵和问题_JAVA代码—算法基础：最大子矩阵的和（N*N的矩阵）

最大子矩阵的和(N\N的矩阵) 题目描述：给定一个n行n列的矩阵，其中 n 的取值范围为 0到100之间的整数，请找到此矩阵的一个子矩阵，并且此子矩阵的各个元素的和最

╰半夏微凉°/ 2022年11月10日 01:17/ 0 赞/ 115 阅读

相关 POJ 1050 最大子段和的延伸最大子矩阵

1050计算最大子矩阵，枚举行（连续的），加到一个一维数组中，再利用一个一维数组求最大子矩阵的方法，得到临时的最大子段和，枚举结束之后，得到的就是整个矩阵的最大子段和了。 j

野性酷女/ 2022年09月30日 03:46/ 0 赞/ 129 阅读

相关 hdu 1081 最大子矩阵和

include<map> include<vector> include<cstdio> include<iostream>

Love The Way You Lie/ 2022年08月03日 11:40/ 0 赞/ 133 阅读

相关 HDU 1505(动态规划-最大子矩阵)

问题描述: Bob is a strategy game programming specialist. In his new city building game the

墨蓝/ 2022年06月06日 01:19/ 0 赞/ 140 阅读

相关 HDU 2870(动态规划-最大子矩阵)

问题描述: Now here is a matrix with letter 'a','b','c','w','x','y','z' and you can change '

浅浅的花香味﹌/ 2022年06月05日 09:07/ 0 赞/ 166 阅读

相关 HDU 1081(动态规划-最大和子矩阵)

问题描述: Given a two-dimensional array of positive and negative integers, a sub-rectangle

秒速五厘米/ 2022年06月02日 07:07/ 0 赞/ 125 阅读

相关子矩阵的最大累加和

![Center][] //子矩阵的最大累加和 public class SubMatrixSum{ //找出最大的子矩阵

迈不过友情╰/ 2022年05月29日 01:11/ 0 赞/ 125 阅读

相关最大子矩阵最大子数组动态规划

最大子矩阵最大子数组动态规划最大子矩阵问题也是动态规划中经典的一道题目（感觉自己到目前为止接触到的只是动态规划的冰山一角，区间dp、数位dp… 还是要花时间

旧城等待，/ 2022年03月15日 04:16/ 0 赞/ 290 阅读

相关最大子序和——最大子矩阵

[LeetCode-最大子序和][LeetCode-] 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:

清疚/ 2022年02月20日 05:52/ 0 赞/ 257 阅读