本隨筆只由于時間原因，我就只寫寫思想了
?
二維數組最大子數組之和，可以 ?引用 ?一維最大子數組之和 的思想
一維最大子數組之和 的思想，在本博客上有，這里就不做多的介紹了

我們有一個最初的二維數組a[n][m]，找它的?最大子數組之和?

1.我們先建立一個新的二維數組b[n][m]

? 二維數組b[j][k] 存放的是a[j][k]（0<=j<n,0<=k<m） 這一點到 a[0][0] ?的最大值

2。循環：從a[0][0]開始 以此是 a[0][1]、?a[0][2]……a[0][m]、
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??a[1][0]、?a[1][1]……a[1][m]、

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??a[2][0]、?a[2][1]……a[2][m]、

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ……

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?a[n][0]、?a[n][1]……a[n][m]、

具體循環工作：

? ? ? ?當循環到a[j][k]（0<=j<n,0<=k<m）

? ? ? ? 則求的是 a[j][k]到 a[0][0] ?的最大值

計算方法：

? ? ? ? ? ?b[j][k]=a[j][k]+b[j-1][k]+b[j][k-1]-b[j-1][k-1]

? ? ? ? ? ?若b[j][k]<0,則賦值為0；

? ? ? ? ? ?每次計算完成后，都需要與max進行比較

當然： ?二位數組邊緣部分循環時需要稍做調整

? ? ? ? ? 當然部分細節也沒說到，留給大家自己考慮

#include<iostream.h> int main() {int i,j;int a[3][3]={-1,-2,1,-3,4,2,3,4,-5};int b[3][3];int max=a[0][0];for(i=0;i<3;i++){for(j=0;j<3;j++){cout<<a[i][j]<<' ';}cout<<endl;}for(i=0;i<1;i++){b[0][0]=a[0][0];for(j=0;j<3;j++){if(a[0][j-1]<0){b[0][j]=a[0][j];}else{b[0][j]=b[0][j-1]+a[0][j];}}}for(i=1;i<3;i++){for(j=0;j<1;j++){if(a[i-1][0]<0){b[i][0]=a[i][0];}else{b[i][0]=b[i-1][0]+a[i][0];}}}for(i=1;i<3;i++){for(j=1;j<3;j++){if(b[i-1][j-1]<0){if(b[i-1][j]>=0&&b[i][j-1]>=0){if(b[i][j-1]>=b[i-1][j]){b[i][j]=b[i][j-1]+a[i][j];}else{b[i][j]=b[i-1][j]+a[i][j];}}else if(b[i-1][j]>=0&&b[i][j-1]<=0){b[i][j]=b[i-1][j]+a[i][j];}else if(b[i-1][j]<=0&&b[i][j-1]>=0){b[i][j]=b[i][j-1]+a[i][j];}else{b[i][j]=a[i][j];}}else{if(b[i-1][j]>=0&&b[i][j-1]>=0){b[i][j]=a[i][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1];}else if(b[i-1][j]>=0&&b[i][j-1]<=0){b[i][j]=a[i][j]+b[i-1][j]-b[i-1][j-1];}else if(b[i-1][j]<=0&&b[i][j-1]>=0){b[i][j]=a[i][j]+b[i][j-1]-b[i-1][j-1];}else{b[i][j]=a[i][j];}}}}for(i=0;i<3;i++){for(j=0;j<3;j++){cout<<b[i][j]<<" ";}cout<<endl;}for(i=0;i<3;i++){for(j=0;j<3;j++){if(b[i][j]>max)max=b[i][j];}}cout<<"max="<<max<<endl;return 0; }

?

完成者： 信1205 李志巖

? ? ? ? ? ? 信1205 張新宇

轉載于:https://www.cnblogs.com/lizhiyan-world/p/3624817.html

總結

以上是生活随笔為你收集整理的求一个二维整数数组最大子数组之和，时间复杂度为N^2的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。