具體問題描述如下
最大子矩陣和問題。給定m行n列的整數矩陣A,求矩陣A的一個子矩陣,使其元素之和最大。
輸入格式:
第一行輸入矩陣行數m和列數n(1≤m≤100,1≤n≤100),再依次輸入m×n個整數。
輸出格式:
輸出第一行為最大子矩陣各元素之和,第二行為子矩陣在整個矩陣中行序号範圍與列序号範圍。
輸入樣例1:
5 6
60 3 -65 -92 32 -70
-41 14 -38 54 2 29
69 88 54 -77 -46 -49
97 -32 44 29 60 64
49 -48 -96 59 -52 25
輸出樣例1:
輸出第一行321表示子矩陣各元素之和,輸出第二行2 4 1 6表示子矩陣的行序号從2到4,列序号從1到6
321
2 4 1 6
分析:
該題是最大子段和問題的拓展,思路是可以将矩陣的多行壓縮成成一行,然後對這一行用求最大子段和的方式求解,這裡和求最大字段和稍微有一點差別,那就是我們不僅要記錄下最大的字段和,還要記錄下該最大字段和的起始位置和終止位置,這個兩個位置就是題目上要求的列序号。而行序号的記錄就是矩陣哪幾行進行壓縮得到的。
11 23 21 12
10 20 45 12
可以壓縮為一行,同一列的進行相加,即
21 43 66 24
#include<iostream>
using namespace std;
#define MAX 101
int colbegin1,colend1,colbegin,colend,rowbegin,rowend;
//對求最大子段和的方法稍作改進,記錄下最大字段的起始位置和終止位置
int Max(int a[],int n){
int max=0,temp=a[1],begin=1,end=1;
for(int i=2;i<=n;i++){
if(temp>0){
temp+=a[i];
end=i;//重新整理終止位置
}
else{
temp=a[i];
begin=end=i;//重置起始位置和終止位置
}
if(temp>max){//記錄下最後的結果,也就是最大值,列序号
max=temp;
colbegin1=begin;
colend1=end;
}
}
return max;
}
int main(){
int n,m,num[MAX][MAX],t[MAX];
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>num[i][j];
int sum,max=0;
for(int begin=1;begin<=n;begin++){
for(int k=1;k<=m;k++)
t[k]=0;//重置為0,這一步非常關鍵
for(int end=begin;end<=n;end++){
for(int k=1;k<=m;k++)
t[k]+=num[end][k];//從開始行到結束行進行壓縮,壓縮成一行
sum=Max(t,m);//求出這一行資料的最大子段和
if(sum>max){//重新整理所要求的結果
max=sum;
rowbegin=begin;
rowend=end;
colbegin=colbegin1;
colend=colend1;
}
}
}
printf("%d\n",max);
printf("%d %d %d %d\n",rowbegin,rowend,colbegin,colend);
return 0;
}
如果覺得有幫助的話,記得點贊或者收藏支援一下嗷 ( :