【LeetCode】Maximum Subarray 解法【Python】

Maximum Subarray leetcode.com

inputの配列の内、隣接する数字の合計が最も高くなる値を求めよ。 制限：O(n)

二重loop使えば簡単に解けるがもちろんそれはダメ。 サンプルのINPUTを可視化すると↓

4, -1, 2, 1 の範囲が最大で6になる。

それぞれ開始位置をずらしてcumsumしていく。 と下記になる。

太字の部分が各列で最大値となり、 太字の中で最大の値は6、つまり4,-1,2,1の数字の合計ということがわかる。

この太字をなぞるようにしてループを回し、最大値を保存すればOK。

さらに制約として、 全て正の場合は単純な合計、全て負の場合は、配列の中の最大値を返すようにして多少の高速化を行う。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        max_ = max(nums)

        if max_ <= 0:
            return max_
    
        if min(nums) > 0:
            return sum(nums)
        
        cumsum = nums[0]
        for num in nums[1:]:
            cumsum = max(num, cumsum + num)
            max_ = max(max_, cumsum)
            
        return max_