d206: 108-Maximum Sum

出處http://zerojudge.tw/ShowProblem?problemid=d206

內容 ：

給你一個 N*N 的陣列，請你找出有最大和的子區域 (sub-rectangle)其和為多少。一個區域的和指的是該區域中所有元素值的和。一個區域是指相連的任意大小的子陣列。範例：

0 -2 -7 0

9 2 -6 2

-4 1 -4 1

-1 8 0 -2

最大子區域：

9 2

-4 1

-1 8

→15

輸入說明 ：

有一個正整數N(N<=100)。從下一列起會有N²個數字。EOF結束。

輸出說明 ：

輸出最大子區域的值。

範例輸入 ：

4

0 -2 -7 0 9 2

-6 2 -4

1 -4 1 -1 8 0

-2 10 9 116 24 -121 30 14 2 119 122 28 -53 125 -71 87 -57 42 -111 125

-33 91 -121 30 -28 1 -16 97 -11 68 -24 103 -126 98 -61 33 48 109

-88 67 -72 77 -107 95 -78 23 -86 45 -4 28 -121 73 -57 20 -122 9

68 -97 79 -68 122 -42 88 -22 0 -116 55 -44 68 -109 43 -32 103 -54

122 -41 62 -114 113 -32 29 -22 99 -11 38 -60 88 -83 28 -83 122 -56

100 -86 63 -49 111 -77 91 -88 69 -110

範例輸出 ：

15

963

提示 ：

出處 ：

ACM 108 (管理：asas)

解題策略

首先計算出從座標(0,0)到 (i,j)的和到sum[i][j]，利用sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];

在找出座標(m,n)，與所有x小於m與y小於n的長方形和的最大值，利用sum[m][k]-sum[m][k-j-1]-sum[m-i-1][k]+sum[m-i-1][k-j-1]