32. Maximum Subarray

読了目安約1分

DP / LeetCode 53 (Medium) — 連続部分配列の最大和。Kadane 法を DP として理解する。

この章の目次

問題

LeetCode 53. Maximum Subarray（Medium / カテゴリ: DP）

整数の配列 nums が与えられます。連続する 1 個以上の要素からなる部分配列のうち、和が最大になるものの和を返してください。要素は負の数を含み、全要素が負のこともあります。

考え方

ヒント 1

状態を dp[i] = 「nums[i] で終わる連続部分配列の最大和」と定めます。答えは dp 全体の最大値です。

ヒント 2

直前までの最大和 dp[i-1] が正なら伸ばし、負なら nums[i] から仕切り直します。遷移は dp[i] = max(nums[i], dp[i-1] + nums[i])、初期条件は dp[0] = nums[0] です。直前の値しか使わないので、配列を持たず変数 2 つで済みます（Kadane 法）。

Swift 実装のポイント

答えの初期値は 0 ではなく nums[0] にします。全要素が負のケースで誤って 0 を返すのを防げます。
nums.dropFirst() で先頭を除いた残りを走査できます。
current（ここで終わる最大和）と best（全体の最大）の 2 変数で空間 O(1) になります。

模範解答

Swift
class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        var current = nums[0]
        var best = nums[0]
        for x in nums.dropFirst() {
            current = max(x, current + x)
            best = max(best, current)
        }
        return best
    }
}

計算量: O(N)。