ACM: 108 - Maximum Sum

這一題是給一個二維陣列，要找出有最大和的子陣列，傳回和的值。原本想不出更好的方法，只好用brute force搜尋所有子陣列 ，但預料之內的Time Limit Exceed(UVa好厲害啊)。查了資料，才知道解決之道在於 Kadane’s Algorithm。

Kadane’s Algorithm可以O(n)找到一維陣列的最大和子序列，Algorithmist上的pseudo code如下：

Kadane's Algorithm(arr[1..n])
begin
    (max, a, b) := (-INFINITY, 0, 0)
    curr := 0
    aa := 1
    for bb := 1 to n do
        curr := curr + arr[bb]
        if curr > max then
            (max, a, b) := (curr, aa, bb)
        endif

        if curr < 0 then
            curr := 0
            aa := bb + 1
        endif
    endfor

    return (max, a, b)
end

即是從陣列頭開始，不斷累加陣列元素值，同時不斷更新最大值，一旦累加和<0，就把累加變數歸零。因為一旦是負數，下一個元素值不管是正數或負數，都只會越加越小，所以不可能會是maximum了。如此，只需要讀過一次陣列就可以找到最大和子序列，真是神奇啊！

CODE

#include <stdio.h>

#define MAX 100

int main(){
  int i, j, k;
  int n, t[MAX][MAX], sum, max;
  
  scanf("%d", &n);
  for(i=0; i<n; i++)
    for(j=0; j<n; j++)
      scanf("%d", &t[i][j]);
  
  /*calculate vertical sum*/
  for(i=0; i<n; i++){
    for(j=1; j<n; j++){
      t[j][i] += t[j-1][i];
    }/*j: row*/
  }/*i: column*/
  
  max = t[0][0];
  /*find max sum*/
  for(i=0; i<n; i++){
    for(j=i; j<n; j++){
      sum = 0;
      for(k=0; k<n; k++){
        if( i==j || i==0 )
          sum += t[j][k];
        else
          sum += ( t[j][k] - t[i-1][k] );
        
        if( sum > max )
          max = sum;
        else if( sum < 0 )
          sum = 0;
      }
    }/*j: ending row*/
  }/*i: starting row*/
  
  printf("%d\n", max);
  exit(0);
}