Kadane's Algorithm とは

配列中の連続する部分配列の最大和を求めるアルゴリズムです.

Kadane's Algorithm の考え方

基本的にDPの考え方です。
よくあるDPでは、更新後に保持される状態は、最も良い状態(この場合、部分配列の最大和)ですが、Kadane's Algorithm では、更新後に保持される状態は、最も良い状態ではなく、現在の要素を含む連続する部分配列の最大和です。

たとえば、A=[1, -2, 3, 4, -5] の場合、

• DP[0] = 1 : 1 だけの部分配列の最大和は 1
• DP[1] = -1 : 1, -2 の部分配列の最大和は 1 ですが、現在の要素(-2)を含む連続する部分配列の最大和は -1
• DP[2] = 3 : 1, -2, 3 の部分配列で、現在の要素を含む配列の最大和は 3 です。
• DP[3] = 7 : 1, -2, 3, 4 の部分配列で、現在の要素を含む配列の最大和は 7 です。
• DP[4] = 2 : 1, -2, 3, 4, -5 の部分配列で、現在の要素を含む配列の最大和は 2 です。

現在の要素を含むというのがポイントです。

コード

A = [1, -2, 3, 4, -5]
DP = [0] * len(A)
DP[0] = A[0]
for i in range(1, len(A)):
    DP[i] = max(DP[i-1] + A[i], A[i])
print(max(DP))  # 7

もしくは常に最大値を保持する変数を用意して、DPの配列を使わずに計算することもできます。

A = [1, -2, 3, 4, -5]
current_max = A[0]
global_max = A[0]
for i in range(1, len(A)):
    current_max = max(current_max + A[i], A[i])
    global_max = max(global_max, current_max)
print(global_max)  # 7

所感

ただ、DPとして理解すると違和感がありますが、現在の要素を含むという条件をつけると、理解できます。
DPとして理解しようとしてかなり違和感を感じたのでメモ。