最大子阵列和
hoj2558,给定一个矩阵,返回最大子矩阵和。
思考(动态规划):
1.读取的同时和矩阵运算部的矩阵
2.枚举矩阵的行上下边界,固定的上,下边界线之后。
按照部分和矩阵O(1)得到同一列元素的和,转化为1维数组的情况
3.依照一维数组的情况,求最大子数组和的思路是:
能够从后往前计算,每次先算以当前元素A[i]为开头的最大和start,
再将start与当前A[i+1:n]所代表的真实最大和进行比較,作为A[i:n]的真实最大和保存起来。
4.输出遍历过程中得到的最大值MAX就可以
cpp代码:
#include<iostream> #define SIZE 102 #define INF 1000 using namespace std; int maxx(int a,int b){ return a>b?a:b; } int main(){ int n,i,j,k,a,c,tmp,MAX,start,all; int num[SIZE]; int mat[SIZE][SIZE]; while(cin>>n){ //读入矩阵的同一时候计算部分和矩阵 for(j=0;j<=n;j++)mat[0][j]=mat[j][0]=0; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ cin>>mat[i][j]; mat[i][j]+=mat[i-1][j];//累积部分和 } } //開始处理 MAX=-INF; for(a=1;a<=n;a++){ for(c=a;c<=n;c++){//枚举上下边界 start=mat[c][n]-mat[a-1][n]; all=start;//先给数组最后一个元素赋值 for(k=n-1;k>=1;k--){//从后往前计算 tmp=mat[c][k]-mat[a-1][k];//依据部分和算出当前元素值 start=maxx(tmp+start,tmp);//先比較以tmp开头的 all=maxx(start,all);//再比較总的 } if(all>MAX)MAX=all; } } cout<<MAX<<endl; } return 0; }
版权声明:本文博主原创文章,博客,未经同意不得转载。
相关文章
- 【算法】【栈和队列模块】求一个[0,1]矩阵中最大的1矩阵面积
- k8s【资源管理】3--LimitRange为命名空间配置 CPU 最小和最大约束
- 还在用Hadoop么?Hadoop服务器造成5PB数据泄露,中国、美国受波及最大!
- H3C 最大跳数16导致网络尺度小
- 程序员必会知识点之 Doherty Threshold (Doherty阈值)App和网站的加载数据的时间用户最大忍受时间是多长
- 力扣解法汇总1026. 节点与其祖先之间的最大差值
- 西数首款PCIe M.2黑盘上市:最大连续读写速度2050MB/s
- 编程的子阵列和最大和膨胀的美(可连接的端到端)
- 中国和印度成为世界上最大的互联网市场
- LINE:今年最大科技IPO 估值69亿美元
- [LeetCode] 1139. Largest 1-Bordered Square 最大的以1为边界的正方形
- Nimble Storage:全闪存阵列是财报中最大亮点