ACM 108 Maximum Sum

要有效地解決二維的Maximum Consecutive Sum必須要先會有效地解決一維的問題
要知道怎麼以O(N)的辦法解決一維的問題，可以去Google一下Kadane's Algorithm

話說每個人說明這個演算法的時候，好像都講的很簡單，可是我都看的霧煞煞的@@"隨便看是覺得很合理，但要是很嚴謹地看，我就會覺得哪裡怪怪的= = 可能是我比較笨的關係吧><


言歸正傳，了解一維的解法後，我們來看看二維要怎麼做

以範例測資為例：
+0 -2 -7 +0
+9+2 -6 +2

 -4+1 -4 +1

-1 +8+0 +2

一個很直覺的想法：暴力求出每個子區域的和
但是暴力要暴力的有效率
以下以(0, 0)~(2,3)表示 
+0 -2 -7 +0
+9+2 -6 +2

 -4+1 -4 +1 這個子區域，其餘以此類推

用暴力法求解一定會要找出(0, x)~(1, y)這幾個子區域中哪個最大
你會發現其實這就是在求
 　　+0 -2 -7 +0
＋)　+9+2 -6 +2
-------------------------
　　 9 0 -13 2 的Maximum Consecutive Sum (可以想想看為什麼，在這邊講解很麻煩，但不難想)

有了這個想法以後，相信要想出有效率的演算法已經不遠了！


#include <stdio.h>

#define N 100

short arr[N][N];

// 取最大值的函數
int max(int a, int b)
{
    if (a > b)
        return a;
    else
        return b;
}

// 解決一維Maximum Consecutive Sum的函數
int max_subarr(int * arr, int n)
{
    int i, max, sum;
  
    sum = max = 0;
    for (i = 0; i < n; i++)
    {
        sum += arr[i];
        if (sum < 0)
            sum = 0;
        else
            if (sum > max)
                max = sum;
    }
  
    return max;
}

int main(void)
{
    int i, j, k, n, tmp, M, sum[N];
  
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            scanf("%hd", &arr[i][j]);
  
    M = 0;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
            sum[j] = arr[i][j];
        tmp = max_subarr(sum, n);
        M = max(tmp, M);
        for (j = i+1; j < n; j++)
        {
            for (k = 0; k < n; k++)
                sum[k] += arr[j][k];
            tmp = max_subarr(sum, n);
            M = max(tmp, M);
        }
    }
  
    printf("%d\n", M);

    return 0;
}