Problem:


Maximum Sum Sequence II

与えられた整数の行列

a1,1 a1,2 ... a1,n
a2,1 a2,2 ... a2,n
:
an,1 an,2 ... an, n

で、縦・横方向に１つ以上連続した項（部分行列）の和の最大値を出力して終了するプログラムを作成して下さい。

Input

入力データは以下の形式で与えられます。

n
a1,1 a1,2 ... a1,n
a2,1 a2,2 ... a2,n
:
an,1 an,2 ... an, n

n は 1 以上 100 以下、ai,j は -10000 以上 10000 以下です。

Output

最大値を 1 行に出力して下さい。

Sample Input 1

3
1 -2 3
-4 5 6
7 8 -9

Output for the Sample Input 1

16

この入力の場合、以下の部分行列の項の和が最大となります。

-4 5
7 8

Sample Input 2

4
1 3 -9 2
2 7 -1 5
-8 3 2 -1
5 0 -3 1

Output for the Sample Input 2

15

この入力の場合、以下の部分行列の項の和が最大となります。

7 -1 5
3 2 -1



Sample input:
3
1 -2 3
-4 5 6
7 8 -9


Sample output:
16

Submission status: Accepted

Solution code:
from itertools import accumulate
n = int(input())
mp = [list(map(int, input().split())) for _ in range(n)]
acc_arr = [list(accumulate([0] + line)) for line in mp]
ans = max([max(line) for line in mp])
for i in range(n + 1):
  for j in range(i + 1, n + 1):
    acc = 0
    for k in range(n):
      add = acc_arr[k][j] - acc_arr[k][i]
      if acc + add > 0:
        acc = acc + add
        ans = max(acc, ans)
      else:
        acc = 0
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = [[0 for i in range(n + 1)] for j in range(n + 1)]

for r in range(n):
    inp = list(map(int, input().split()))
    for c in range(n):
        s[r + 1][c + 1] = inp[c] + s[r][c + 1]

ans = -10001

for r_end in range(1, n + 1):
    for r_start in range(r_end):
        dp = [-10001]
        for c in range(1, n + 1):
            s_tmp = s[r_end][c] - s[r_start][c]
            dp.append(max(dp[c - 1] + s_tmp, s_tmp))
        ans = max(ans, max(dp))
print(ans)