更多精彩文章請關注公眾號『大海的BLOG』
問題
給定一個nxm的矩陣A，求A中的一個非空子矩陣，使這個子矩陣中的元素和最大，
其中，A的子矩陣指在A中行和列均連續的一塊，
輸入格式
輸入的第一行包含兩個整數n, m，分別表示矩陣A的行數和列數，
接下來n行，每行m個整數，表示矩陣A，
輸出格式
輸出一行，包含一個整數，表示A中最大的子矩陣中的元素和，
樣例輸入
3 3
-1 -4 3
3 4 -1
-5 -2 8
樣例輸出
10
樣例說明
取最后一列，和為10，
資料規模和約定
對于50%的資料，1<=n, m<=50；
對于100%的資料，1<=n, m<=500，A中每個元素的絕對值不超過5000，
思路
這題我是用動態規劃求解，如下圖，假設最大子矩陣的結果為從第r行到k行、從第i列到j列的子矩陣，如下所示(ari表示a[r][i],假設陣列下標從1開始)：
| a11 …… a1i ……a1j ……a1n |
| a21 …… a2i ……a2j ……a2n |
| ......................|
| ...................... |
| ar1 …… ari ……arj ……arn |
| ......................|
| ...................... |
| ak1 …… aki ……akj ……akn |
| ......................|
| an1 …… ani ……anj ……ann |
那么我們將從第r行到第k行的每一行中相同列的加起來，可以得到一個一維陣列如下：
(ar1+……+ak1, ar2+……+ak2, ……,arn+……+akn)，那么從中我們就可以把一個求子矩陣 的問題轉換成一個求最大子段和 的問題，從中求出解，那么問題又來了，什么是最大子段和？怎么求最大子段和？
首先，我們看一個問題：
給定n個整數（可能為負數）組成的序列a[1],a[2],a[3],…,a[n],求該序列如a[i]+a[i+1]+…+a[j]的子段和的最大值
比如當（a1,a2,a3,a4,a4,a6）=(-1,11,-1,13,-5,-2)時，最大子段和就為23，
用動態演算法求解:
**b[j]=max{a[i]+a[j]},1<=i<=j,且1<=j<=n,則所求的最大子段和為max b[j]，1<=j<=n，
由b[j]的定義可易知，當b[j-1]>0時b[j]=b[j-1]+a[j]，否則b[j]=a[j]，故b[j]的動態規劃遞回式為:
b[j]=max(b[j-1]+a[j],a[j])，1<=j<=n，
最大子段和演算法
int getMaxArray(int a[],int n){//求最大子段和
int max=a[0],temp=0;
for (int i=0;i<n;i++) {
if (temp>0) {
temp+=a[i];
}else {
temp=a[i];
}
max=max>temp?max:temp;
}
return max;
}
實作代碼
#include "stdio.h"
#include<string.h>
int dp[100];
int getMaxArray(int a[],int n){//求最大子段和
int max=a[0],temp=0;
for (int i=0;i<n;i++) {
if (temp>0) {
temp+=a[i];
}else {
temp=a[i];
}
max=max>temp?max:temp;
}
return max;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
int a[n][m];
for(int i=0;i<n;i++){
for (int j=0;j<m;j++) {
scanf("%d",&a[i][j]);
}
}
int res=a[0][0],tmp;
for (int i=0;i<n;i++) {
memset(dp, 0, sizeof(dp));//將dp陣列置為0
for (int j = i; j < n; ++j) {
for (int k = 0; k < m; ++k) {
dp[k] += a[j][k];
}
tmp = getMaxArray(dp, n);
res = res > tmp ? res : tmp;
}
}
printf("%d\n", res);
}
更多精彩文章請關注公眾號『大海的BLOG』
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/36295.html
標籤：C
上一篇：藍橋杯-四平方和問題
下一篇：C語言二維陣列超細講解