最大子矩阵（动态规划）

忘是亡心i 2022-06-07 12:50 406阅读 0赞

最大矩阵和顾名思义，就是一个矩阵和最大，例如下面的矩阵

0 -2 -7  0
     9  2 -6  2
    -4 1 -4 1 -1 8 0 -2

最终找到了和为15的矩阵

9 2
    -4 1 -1 8

所选的矩阵没有规定，只要在这个大矩阵中，就可以了，那么我们需要限定它的行和列；  
我们用三个for循环把所有的行的情况枚举，分别是i，j，k  
**i从0开始，代表开始的行，**  
**j从i 开始，代表从i行开始变化，**  
**k从0开始，代表列的变化。**  
这样的话我们还需要找出变化的列，然后计算它的和  
我们已经知道了最优解一定在i，j之间（遍历肯定能找到），如果我们事先求得了**每一列的和**，然后在这个一位数组中找和最大的子段，对应的列就是我们需要的列。  
什么意思呢，例如

9  2 -6  2
    -4 1 -4 1 -1 8 0 -2

i=1，j=3的时候，已经确定了最优解的行数，然后把**每一列求和**，得到一维数组

4 11 -10 1

求出最大子段和，4 + 11 = 15，这样的话就不需要去枚举列的变化了。  
我们需要维护一个一维数组来存储，写一个求最大子段和的函数就ok了

int maxarray(int *a, int n) {
       //子段和
        int each = a[0];
        int maxx = a[0];
        for(int i = 1; i < n; i++) {
            if(each >= 0) each += a[i];
            else each = a[i];
            if(each > maxx) maxx = each;
        }
        return maxx;
    }
    
    int maxdoulearray(int (*a)[maxn], int n) {
        int max1, max2, each[maxn];
        memset(each, 0, sizeof each); //初始化，一维数组
        max1 = max2 = a[0][0];
        for(int i = 0; i < n; i++) {
            memset(each, 0, sizeof each);
            for(int j = i; j < n; j++) {
                for(int k = 0; k < n; k++) {
                    each[k] += a[j][k];//求好每一列的和
                }
                max1 = maxarray(each, n);//每求好一列就计算
                                        //因为是+=，所以求下一列的时候保存着上一列的和
                if(max1 > max2) max2 = max1;
            }
        }
        return max2;
    }