詳細(xì)思路鏈接：https://www.cnblogs.com/GodA/p/5237061.html

問(wèn)題描述：

給定一個(gè)n×m?的矩陣A，求A?中的一個(gè)非空子矩陣，使這個(gè)子矩陣中的元素和最大。其中A?的子矩陣指在A?中行和列均連續(xù)的一部分。

輸入格式

輸入的第一行包含兩個(gè)整數(shù)n,m(1≤n,m≤50)，分別表示矩陣?AA?的行數(shù)和列數(shù)。

接下來(lái)n?行，每行m?個(gè)整數(shù)，表示矩陣Ai,j?(?1000≤Ai,j?≤1000)。

輸出格式

輸出一行，包含一個(gè)整數(shù)，表示A?中最大子矩陣的元素和。

樣例輸入

3 3 2 -4 1 -1 2 1 4 -2 2

樣例輸出

6


代碼： /*思路剖析： 最大子矩陣 注意任意行列連續(xù)就拿3*3矩陣為例共有 9 (單個(gè)元素)+12（兩個(gè)元素）+6 （三個(gè)元素）+4 （六個(gè)元素）+1 （九個(gè)元素）=32種子矩陣模式！// 此題的關(guān)鍵就是如何選取。我們知道矩陣的維數(shù)為動(dòng)態(tài)變化過(guò)程，但是在挖取子矩陣的過(guò)程中，一定是綁定“行”或“列”這個(gè)要素。//具體舉例而言：對(duì)于矩陣 M = {2，-4, 1；-1，2, 1；4，-2，2 } 單個(gè)元素時(shí)，我們似乎只要求元素最大值即可；非單個(gè)元素時(shí)，我們會(huì)考慮行或者列：兩個(gè)：（2，-4）或（2，-1）等 三個(gè)：（2，-4,1）或（2，-1,4）等 六個(gè)：{2，-4,1；-1,2,1}或{2，-4；-1，2；4，-2}等 九個(gè)：M我們發(fā)現(xiàn)這樣一個(gè)規(guī)律（行的效果等同于列）：可以定義出一個(gè)值動(dòng)態(tài)變化的三維數(shù)組。它的三個(gè)值分別對(duì)應(yīng)第i行第k列到第j行第k列的元素和（其中i，j，k 均=0,1,2） 其中 j 的取值由 i 影響 代碼細(xì)說(shuō)。 */ #include <iostream> #include <cstring>using namespace std;int n,m; int dp[300][300],arr[300];int MAX(int a[],int n){int max=-1000000;for(int i=0;i<n;i++){int tmpmax=0;for(int j=i;j<n;j++){tmpmax+=a[j];if(tmpmax>max)max=tmpmax;}}return max; }int main() {cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>dp[i][j];}}int maxsub=-1000000,maxarr=0;for(int i=0;i<n;i++){memset(arr,0,sizeof(arr));for(int j=i;j<n;j++){int k;for(k=0;k<m;k++){arr[k]+=dp[j][k];}maxarr=MAX(arr,k);/*在這里wa了好幾次，第一次是放在該循環(huán)的外面了，第二次發(fā)現(xiàn)k寫(xiě)成n了，要是寫(xiě)成n計(jì)算的數(shù)就變多了*/if(maxarr>maxsub) maxsub=maxarr;}}cout<<maxsub<<endl;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Fy1999/p/9332798.html

總結(jié)

以上是生活随笔為你收集整理的最大子阵的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。