求一个二维数组的最大子矩阵的和

要求：

• 输入一个二维整形数组，数组里有正数也有负数。

• 二维数组中连续的一个子矩阵组成一个子数组，每个子数组都有一个和。

• 求所有子数组的和的最大值。

设计思路： 使用“最笨方法”，考虑以每个数据开始的每个子矩阵。思路简单，效率极低。

实现语言：Java

源代码如下：

    /*
     * row,col分别为数组行数和列数
     * source_row,source_col为子矩阵的起始位置
     * edge_row,edge_col分别为行列边界
     * */
    public static int row = 5,col = 5;
    public static int source_row = -1,source_col = -1,edge_row = -1,edge_col = -1;
    
    public static void main(String[] args){
        int a[][] = new int[row][col];
        
        // 随机赋值
        System.out.println("总矩阵为：" + "
");
        for(int i = 0;i < row;i++){
            for(int j = 0;j < col;j++){
                a[i][j] = (int)(Math.random() * 20 - 10);
                if(a[i][j] >= 0)
                    System.out.print(" ");
                System.out.print(a[i][j] + " ");
            }
            System.out.print("
");
        }
        
        

        /* 
         * 依次循环每行每列的每个数据项
         * 寻找每个数据项能组成的子矩阵之和
         * 更新赋值m和n分别为每次计算行列的边界
         * 即每次计算a[i][j] 从i~m行,j~n列的子矩阵的和
         * */
        int sum = a[0][0],sum_temp = 0;
        for(int i = 0;i < row;i++){
            for(int j = 0;j < col;j++){
                int m = i,n = j;
                while(m < row){
                    while(n < col){
                        for(int k = i;k <= m;k++){
                            for(int l = j;l <= n;l++){
                                sum_temp = sum_temp + a[k][l];
                            }
                        }
                        if(sum_temp > sum){
                            sum = sum_temp;
                            source_row = i+1;
                            source_col = j+1;
                            edge_row = m+1;
                            edge_col = n+1;
                        }
                
                        sum_temp = 0;
                        n++;
                    }
                    m++; 
                    n = j;  // 重置m边界
                }
            }
        }
        
        System.out.println("
" + "最大子矩阵的和为：" + sum);
        System.out.println("
" + "最大子矩阵的起点为：" + source_row + "行" + source_col + "列" + "
" 
                +"边界为：" + edge_row + "行" + edge_col + "列");
        
    }

运行结果：

个人总结：那些不被人看重的所谓的“最笨方法”并不是很容易实现。要学会熟练运用N多for循环的套用。