Maximum Subarray Problem(最大部分配列問題) memo(Kadane's algorithmの理解)

Maximum Subarray Problem(最大部分配列問題)

Maximum Subarray Problemとは、
与えられた配列に対して、総和が最大になる部分配列を求める問題です。

これの解法として、Kadane's algorithmというものがあり、
計算量O(n)にて解を求めることができるというものです。

アルゴリズムの解説は多くありますが、自分の理解をメモ

Kadane's algorithm sample

python3

def maxSubArray(self, nums: List[int]) -> int:
    dp = [0 for _ in range(len(nums))]
    dp[0] = nums[0]
    for i in range(1, len(nums)):
        dp[i] = max(dp[i-1]+nums[i], nums[i])
    return max(dp)

解説

以下のステップで求められる。

1. numsの任意の要素から要素iまでの総和の最大値をdp[i]に格納
   dp[0]:任意の要素から要素0までの総和の最大値
   　　　(要素0の値が格納される)
   dp[1]:任意の要素から要素1までの総和の最大値
   　　　(要素0までの最大値(dp[0])+要素1」 か 「要素1のみ(要素1からSubarrayを始める)」のうち大きい方)
   dp[2]:任意の要素から要素2までの総和の最大値
   　　　(要素1までの最大値(dp[1])+要素2」 か 「要素2のみ(要素2からSubarrayを始める)」のうち大きい方)
   以降繰り返し

2. dpの最大値を求める

dpには各要素iまでの部分配列の和の最大値が格納されるので、
dpの最大値を求めることでMaximum Subarray Problemの解が求められる