問題

LeetCode 53. Maximum Subarray:
- https://leetcode.com/problems/maximum-subarray/

解法

Kadane's algorithmで解く。動的計画法なので部分問題に分割する。部分問題は下記のように定義する。

list の 0 から n までの間で、listのn番目の要素を含んだ 最大部分配列

愚直にコードで書くとこうなる。

func maxSubArray(_ nums: [Int]) -> Int {
      var dp = [Int](repeating: -1, count: nums.count)
      dp[0] = nums[0]
      for i in 1..<nums.count {
          dp[i] = max(dp[i-1] + nums[i], nums[i]) // relaxation
      }
      return dp.max()!
}

ポイント

部分問題の定義にて「n番目の要素を含んだ」部分配列の総和という考えがキモとなる。

例えば、下記のケースを考える

list = [10, -11, 21, 40]

そして、n=2のときの選択肢は下記のどちらかになる。

0~n-1までの配列を含めると、 20 (= 10 + -11 + 21 )
0~n-1までの配列を含めないと、 21

この場合は最大数の21が選択される

改善

一般的な動的計画法だと答えは大抵は dp の末尾に答えが入るケースが多いけど、このケースの場合は必ずしもそうならない。

なぜなら、dp に保存されてるのは「nを含む」0~nの中の最大配列総和だから。dpの末尾だと「必ずn番目の要素を含んだ最大部分配列」が答えとして出てくる。

なので、return するときに、dpの中からmax で探してる。

  return dp.max()!

改善として、for の中で合わせてmaxも保存しておく。そうなると、O(2n)からO(n)になる。

最終的にコードは下記のようになる。

  func maxSubArray(_ nums: [Int]) -> Int {
      var dp = [Int](repeating: -1, count: nums.count)
      dp[0] = nums[0]
      var maxSoFar = nums[0] // <= 追加
      for i in 1..<nums.count {
          dp[i] = max(dp[i-1] + nums[i], nums[i])
          maxSoFar = max(maxSoFar, dp[i]) // <= 追加
      }
      return maxSoFar 
  }

REF