/*控制i,枚举所有的子矩阵。将每一个字矩阵的列全都累加到最上端,然后将子矩阵的最上端当做一维的最大子段和。
只需求出所有子矩阵的最大和即可。*/
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
int a[101][101];
int maxsum(int n,int *a)
{
int sum=-129,b=0;
for(int i=0; i<n; i++)
{
if(b>0) b+=a[i];
else b=a[i];
if(b>sum) sum=b;
}
return sum;
}
int maxsum1(int n)
{
int ans=-100000000;
int sum;
int b[101];
for(int i=0; i<n; i++)
{
memset(b,0,sizeof(b));
for(int j=i; j<n; j++)
{
for(int k=0; k<n; k++)
{
b[k]+=a[j][k];//放到最上端,按列进行储存
}
sum=maxsum(n,b);
if(sum>ans) ans=sum;
}
}
return ans;
}
int main()
{
int n;
while(scanf("%d",&n)==1)
{
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
scanf("%d",&a[i][j]);
printf("%d\n",maxsum1(n));
}
return 0;
}
分享到:
相关推荐
1001 计算直线的交点数 1002 FatMouse's Speed1003 Common Subsequence1004 Max Sum 1005 Super Jumping! Jumping! Jumping! 1006 免费馅饼 1007 Humble Numbers1008 Monkey and Banana 1009 龟兔赛跑 1010 数塔
1.Fibonacci Numbers 2.矩阵连乘问题 3.MAX SUM 4.最长公共子序列 5.Number Triangles 6.编辑距离问题 7.Pebble Merging 8.租用游艇问题 . .
max sum series 最大子数组:两个指针算法。 可以认为是一维DP。 有一个分而治之的解决方案,分为三个场景。 最大子数组 II :划分左右。 2 X 1D DP 最大子阵列 III : 2D DP 优化 最大乘积子数组:使用最大值和...
max and min element of an array 4. Given an array which consists of only 0, 1 and 2. Sort the array without using any sorting algo 5. Move all the negative elements to one side of the array 6. Find ...
struct DP { int num; int sum; } d[50000]= {0}; int max=0; void qsort(int low,int high,struct DP key[]) { int i=low,j=high; struct DP tag=key[i]; if(i) { do { while(tag.num[j].num && i) j--; ...
然后递推出max_sum(1),也就是最后的结果了。 依此,我们可以写一个for循环,从数组的最后往前,依次递推,并保存最大值: public int maxSubArray(int[] nums) { int max = nums[nums.length - 1]; int lastMaxSum ...
sum c LeetCode There is my accpted JAVA and C solution Index Title Solution Difficulty days 1 Easy \ 2 Easy \ 3 Easy \ 4 / Easy 2/17 5 / Easy 2/17 6 Easy 2/17 7 Easy 2/26 8 Easy 2/26 9 Easy 2/26 10 ...
leetcode 2 Useful Links ...Sum], [17 Phone Num] [] BFS [] [] [] DP , [53 max subarray], , [96 DP | BST], , [] [] Binary Search , , [74 2D matrix] [] Slicing Window / Two Pointers [918 Ma
sum 使用 hash 表来记录已经存储的数据,新来的数据与 target 做差,判断是否在 hash 表中存在 3. 无重复字符的最长子串 这道题目可以使用 128 位的数组来表示所有字符。开始每个字符都初始化为-1 然后这道题目其实...
subarray_max.py 找到具有最大和的连续子数组(至少包含一个数字) 5/13 做我的游戏项目:CityFromNaught 5/14 多数元素.py roman_to_integer.py integer_to_roman.py 5/15 longest_common_prefix.py longest_...
1028 Flip and Shift 简单题,可以DP/BFS/……,但是实际上有数学方法可直接判断出来 1026 Modular multiplication of polynomials 简单题,有比较简单的好算法 1307 Packets 简单题,不过也蛮经典的…… 1312 ...
1028 Flip and Shift 简单题,可以DP/BFS/……,但是实际上有数学方法可直接判断出来 1026 Modular multiplication of polynomials 简单题,有比较简单的好算法 1307 Packets 简单题,不过也蛮经典的…… 1312 ...
371 | [Sum of Two Integers](https://leetcode.com/problems/sum-of-two-integers/) | [C++](./C++/sum-of-two-integers.cpp) [Python](./Python/sum-of-two-integers.py) | _O(1)_ | _O(1)_ | Easy | LintCode | ...
C FORDIV(NP,ND,PM,DP,DM,WJ), COMPUTES THE FORWARD FUNCTION AS DOES FORMOD() C BUT ALSO RETURNS THE MATRIX OF PARTIALS, WJ(ND,NP). C OBJMAT(IRUF, DEL, NPEN), ASSEMBLES THE PENALTY MATRIX (THIS WILL BE ...