子矩陣的最大累加和問題

【題目】

給定一個矩陣matrix，其中的值有正負0，傳回子矩陣的最大累加和。

【舉例】

例如，matrix為：

-90 48 78

64 -40 64

-81 -7 66

其中，最大累加和的子矩陣為：

48 78

-40 64

-7 66

是以傳回209

matrix為：

-1 -1 -1

-1 2 2

-1 -1 -1

其中，最大累加和的子矩陣為：

2 2

是以傳回累加和4

【代碼】

public static void main(String[] args) {
        int[][] arr={{-,,},{,-,},{-,-,}};
        System.out.println(maxSum(arr));//209
        int[][] arr1={{-,-,-},{-,,},{-,-,-}};
        System.out.println(maxSum(arr1));//4

    } 

    //子矩陣的最大累加和問題
    public static int maxSum(int[][] m){
        if(m==null||m.length==||m[].length==){//判斷矩陣非空
            return ;
        }
        int[] s=null;//累加數組
        int cur=;
        int max=Integer.MIN_VALUE;
        for(int i=;i!=m.length;i++){//從第i行元素開始，往下查找所有子矩陣
            s=new int[m[].length];
            for(int j=i;j!=m.length;j++){
                cur=;
                for(int k=;k!=m[].length;k++){
                    s[k]+=m[j][k];//每一步的累加數組（疊加每一列）
                    cur+=s[k];
                    max=Math.max(cur, max);//每一步的最大子矩陣的累加和
                    cur=cur>?cur:;
                }
            }
        }
        return max;
    }