NYOJ 104-最大和【模板:最大子阵和】 妖狐艹你老母 2022-07-24 08:07 147阅读 0赞 ## 最大和 ## 时间限制:1000 ms | 内存限制:65535 KB 难度:5 描述 给定一个由整数组成二维矩阵(r\*c),现在需要找出它的一个子矩阵,使得这个子矩阵内的所有元素之和最大,并把这个子矩阵称为最大子矩阵。 例子: 0 -2 -7 0 9 2 -6 2 \-4 1 -4 1 \-1 8 0 -2 其最大子矩阵为: 9 2 \-4 1 \-1 8 其元素总和为15。 输入 第一行输入一个整数n(0<n<=100),表示有n组测试数据; 每组测试数据: 第一行有两个的整数r,c(0<r,c<=100),r、c分别代表矩阵的行和列; 随后有r行,每行有c个整数; 输出 输出矩阵的最大子矩阵的元素之和。 样例输入 1 4 4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 样例输出 15 来源 [\[苗栋栋\]原创][Link 1] 上传者 [苗栋栋][Link 2] #include<stdio.h> #include<string.h> #include<algorithm> #define MAXN 102 using namespace std; int maxsum(int m,int n,int mat[MAXN][MAXN]) { int matsum[MAXN][MAXN+1],ret,sum; int i,j,k; for(i=0;i<m;i++) { for(matsum[i][j=0]=0;j<n;j++) { matsum[i][j+1]=matsum[i][j]+mat[i][j]; } } for(ret=mat[0][j=0];j<n;j++) { for(k=j;k<n;k++) { for(sum=0,i=0;i<m;i++) { sum=(sum>0?sum:0)+matsum[i][k+1]-matsum[i][j],ret=(sum>ret?sum:ret); } } } return ret; } int main() { int num[MAXN][MAXN]; int r,c,t; scanf("%d",&t); while(t--) { scanf("%d%d",&r,&c); for(int i=0;i<r;i++) { for(int j=0;j<c;j++) { scanf("%d",&num[i][j]); } } int ans=maxsum(r,c,num); printf("%d\n",ans); } return 0; } [Link 1]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%5B%E8%8B%97%E6%A0%8B%E6%A0%8B%5D%E5%8E%9F%E5%88%9B [Link 2]: http://acm.nyist.net/JudgeOnline/profile.php?userid=%E8%8B%97%E6%A0%8B%E6%A0%8B
相关 最大子阵 `` <table> <tbody> <tr> <td> <div> <strong><span style="font-size:1 今天药忘吃喽~/ 2024年02月17日 18:43/ 0 赞/ 30 阅读
相关 最大子序和 最大子序和 1、参考资料 https://leetcode-cn.com/problems/maximum-subarray/ 2、题目要求 > 题目描述 古城微笑少年丶/ 2022年12月05日 10:13/ 0 赞/ 157 阅读
相关 最大子序列和 最大子序列和的4种算法 给定整数A1,A2…An(可能有负数)求最大子序列和。(假设所有整数均为负数时,最大子序列和为0) Arg1 public int 一时失言乱红尘/ 2022年08月04日 04:18/ 0 赞/ 165 阅读
相关 NYOJ 104-最大和【模板:最大子阵和】 最大和 时间限制:1000 ms | 内存限制:65535 KB 难度:5 描述 给定一个由整数组成二维矩阵(r\c),现在需要找出它的一个子矩阵,使得这个子矩阵内 妖狐艹你老母/ 2022年07月24日 08:07/ 0 赞/ 148 阅读
相关 最大子序列和 -------------------- 给定一个整数数组 `nums` ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入 淡淡的烟草味﹌/ 2022年05月22日 11:56/ 0 赞/ 161 阅读
相关 最大子序和 给定一个整数数组 `nums` ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5 妖狐艹你老母/ 2022年04月16日 02:12/ 0 赞/ 180 阅读
相关 最大子向量和 何海涛:《剑指Offer:名企面试官精讲典型编程题》:九度OJ 题目描述:[http://ac.jobdu.com/problem.php?cid=1039&pid=14][ 柔光的暖阳◎/ 2022年03月20日 03:24/ 0 赞/ 124 阅读
相关 最大子序和——最大子矩阵 [LeetCode-最大子序和][LeetCode-] 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 清疚/ 2022年02月20日 05:52/ 0 赞/ 260 阅读
相关 最大子序和 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4 川长思鸟来/ 2022年01月20日 04:09/ 0 赞/ 220 阅读
相关 最大子段和 送分题(songfen) Time Limit:1000ms Memory Limit:128MB 题目描述 LYK喜欢干一些有挑战的事,比如说求区间最大子段和。它知 港控/mmm°/ 2022年01月10日 10:53/ 0 赞/ 212 阅读
还没有评论,来说两句吧...