ALGO-maxnum sum of sub matrix/sub array

題目：

Given an n by n two-dimensional array arr (1 < = n < = 100) of arbitrary integers, find the maximum sub-array. Maximum sub-array is defined to be the sub-array whose sum of integer elements are the maximum possible.

想法：

以暴力法思考：

int sum=0;

for(i=0~n-1)

    for(j=0~n-1)

        for(p=0~n-1)

            for(q=0~n-1)

                for(s=i~p)

                    for(t=j~q)

                        sum = sum+M[s][t];

若是窮舉n*n中所有的子矩陣和，時間複雜度是O(n^6)。

但這是一個DP approach題目(對不起...我不知道什麼是DP approach...)。

假設給予一個n*n矩陣M，element值可正可負，則我創建另一n*n矩陣S，其中S[i][j]值為M[0][0]~M[i][j]所有元素的和：S[i][j] = M[i][j]+S[i-1][j]+S[i][j-1]-S[i-1][j-1]，若i-1<0或j-1<0則該項忽略，初始值S[0][0]=M[0][0]。

for(i=0~n-1)

    for(j=0~n-1)

        S[i][j] = M[i][j]+S[i-1][j]+S[i][j-1]-S[i-1][j-1];

則問題演變成：右圖是一矩陣M，紅色區域是任取一個想要計算的範圍(i,j)~(p,q)，可以看成從藍色方塊-兩個綠色方塊+橘色方塊，而這些方塊的和已經在S中，則計算從任意(i,j)~(p,q)子矩陣和的方法 = S[p][q]-S[p][j-1]-S[i-1][q]+S[i-1][j-1]

演算法：

for(i=0~n-1)

    for(j=0~n-1)

        for(p=0~n-1)

            for(q=0~n-1)

                sum = S[p][q]-S[p][j-1]-S[i-1][q]+S[i-1][j-1];

複雜度：

1.建立S矩陣 : O(n^2)

2.DP計算最大子矩陣和 : O(n^4)

----------------------------------------

+                                     = O(n^4)

類似問題：最大/最小子矩陣和

UVa108