大家好,又见面了,我是全栈君。
这篇是看了别人的报告写的,就当是屡屡思路好了.
题目大意。给定一个n阶矩阵(方阵),每一个元素中存在一个数字.任务就是求出一个最大的子矩阵使得矩阵元素之间的和是最大的.
n=100;
1.矩阵A[m][n]的和能够直接 sum+=A[i][j] ( i = 0 to n-1 j=0 to n-1); 还能够求出第i列的和p[i],再将所在列加起来,(当然行是同理的).
2.因此所选的矩阵的行k能够枚举(0<=k<=n-1),此时能够现将列加起来,然后找到这些列中连续最大和就可以.这就是选出的矩阵最大和.
3.在全部矩阵中选出最大和的一个。
/*Source Code Problem: 1050 User: Memory: 388K Time: 32MS Language: GCC Result: Accepted Source Code*/ #include <stdio.h> int max(int a,int b){ return a>b?a:b; } int main(){ int i,j,k,n; int ans=-0xfffffff; int A[101][101]={0}; scanf("%d",&n); for(i=0;i<n;i++){ for(j=0;j<n;j++){ scanf("%d",&A[i][j]); } } for(i=0;i<n;i++){ for(j=0;j<n;j++){ int add[101]={0},d[101]={0}; for(k=0;k<n;k++){ int l; for(l=i;l<=j;l++){ add[k]+=A[l][k]; } } d[0]=add[0]; ans=max(ans,d[0]); for(k=0;k<n;k++){ d[k]=d[k-1]>0?d[k-1]+add[k]:add[k]; ans=max(ans,d[k]); } } } printf("%d\n",ans); return 0; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115265.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...