問題
- LeetCode 53. 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
}