ACM 108 Maximum Sum

難題……直接用暴力硬幹會花O(n ^ 6)的時間，直接TL =.=。
後來查了很多資料，看人家的想法等等。
才發現到，原來Maximum subarray problem，
已經有人在研究。一維list，可以用O(n)就找出max sum。
這個方法稱為Kadane's algorithm。
而二維套用一維的概念，就可以花O(n ^ 3)的時間找出max sum。
解法主要參考這裡。
另外要講一下，algorithmist的解法應該是正確的，
但是prefix sum應該會花O(n ^ 3)的時間建立。我覺得algorithmist寫得太簡略，
以至於讓人看不懂（或是誤解）。

主要想法：對於一維陣列，
我們可以使用Kadane's algorithm以O(n)的方式求出max sum。
所以二維陣列，可以用一維陣列的方式求解。
例如題目給的陣列
0 -2 -7 0 (1)
9 2 -6 2 (2)
-4 1 -4 1 (3)
-1 8 0 -2 (4)
其實可以看成10個子陣列（皆一維）
這些陣列分別是
(1)、(1) + (2)、(1) + (2) + (3)、(1) + (2) + (3) + (4)、
(2)、(2) + (3)、(2) + (3) + (4)、
(3)、(3) + (4)、
(4)。
從這十個一維陣列中找出max sum，即是答案。
建立子陣列需要花O(n ^ 2)的時間，而每個陣列需要花O(n)的時間找sum。
所以總共要花O(n ^ 3)的時間。

Kadane's algorithm滿像我解ACM661找最大電流的方法，
不過Kadane's algorithm更精確……令人佩服！
Kadane's algorithm的說明可以看wiki python實作，
或是Algorithm的code實作，
可以一目了然其運作原理。
這裡也有解釋Kadane's algorithm。
（但不要看他的code，是錯的……雖然AC）
uva toolkit的output也是錯的……。

/* ACM 108 Maximum Sum
 * mythnc
 * 2011/10/28 21:31:21   
 * run time: 0.008
 */
#include <stdio.h>
#include <string.h>

#define MAXN 100

void subsum(int, int);

int s[MAXN][MAXN];
int colsum[MAXN];
int max;

int main(void)
{
    int n, i, j;

    scanf("%d", &n);
    /* init */
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            scanf("%d", &s[i][j]);

    max = -12701;
    for (i = 0; i < n; i++) {
        for (j = i; j < n; j++)
            subsum(j, n);
        /* clear colsum's content */
        memset(colsum, 0, sizeof(int) * n);
    }

    printf("%d\n", max);

    return 0;
}

/* subsum: calculate the sub-rectangle value */
void subsum(int row, int n)
{
    int i, j, sum;

    for (i = 0; i < n; i++)
        colsum[i] += s[row][i];
    /* Kadane's algorithm (modified) */
    for (i = sum = 0; i < n; i++) {
        sum += colsum[i];
        if (sum > max)
            max = sum;
        if (sum < 0)
            sum = 0;
    }
}