二维数组最大子数组的求和

      民哥的花花点子永远层出不穷,在求了一位数组最大子数组和后,他又推出了求二位数组最大子数组的和,一位数组求和我们采用暴力枚举法,结果想法来得很快,但是时间复杂度却很高,其实在求二维数组最大子数组之和的最初想法,我们也想到了暴力,但很快我们就把他pass掉了,我们要有自己新的idea,我们假想首先将二维数组看成多个一维数组,分别用一维数组求最大和的方法,求出各组的最大值,最小值的模块,同时标记各模块的(i,j)起始与终止的位置,先以第一行一维数组的最大模块的(i,j)为边界依次加上第二行,第三行……此时会有一个以第一行最大模块为“带头大哥”的最大模块,记录此时为模块1;第二次,以第二行数组的最大和为模块边界,依次加上第三行,第四行……此时会有一个以第二行为“带头大哥”的最大模块,记录为模块2,依次求出模块n,通过比较得出最大模块,此时的模块就应当为整个二维数组的最大模块,但这只是我和小伙伴儿(洋哥)的设想,草图如下:

 

俗话说理想很丰满,现实很骨感,我们算是真真的体会到了,实现起来可没有那么容易,

一维的数组的求最大和的模块:

 int max(int a[],int n) {
    cur
= a[0];
    max
= a[0];
   
for i=1 to n-1 do
        if cur<0 do
           { cur
= 0;ix=i;}
        {cur
+= a[i];iy=i;}if cur>max do
            max
= cur;
   
return max;
}

 这虽然也是暴力枚举的一种,但是大大简化了枚举范围,但是我们水平有限啊,望园友们多多指教。

原文地址:https://www.cnblogs.com/xinshang/p/3611913.html