天天看點

最大子矩陣和問題(動态規劃)

具體問題描述如下

最大子矩陣和問題。給定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;
}
           

如果覺得有幫助的話,記得點贊或者收藏支援一下嗷 ( :

繼續閱讀