【LeetCode】53. Maximum Subarray 5日目

どーも！

たかぽんです！

今回は53. Maximum Subarrayを解いたので、ざっくり解説書いておきます...!

53. Maximum Subarray

Maximum Subarrayの問題は以下です。

ざっくりとどう言うことか説明すると、配列の中で、隣り合う要素を足した際、どういった組み合わせが一番大きくなるのか、その大きな値を返すプログラムです。

ちょっと言葉だけではわかりづらいので、例を...

公式の例からお借りすると...

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

上記の場合、nums[3] からnums[6]までを足し合わせると、6になります。

これは、numsの他の隣り合う要素を足した全てのパターンよりも大きくなるため、その和の6が答えになります。

言い方を変えると、nums[a]からnums[b]までの和で、最も大きくなるa, bを探し、その和を出す...といった感じですね。

アルゴリズム

さて、これは考えるのがとても難しかったです...

極論ですが、[1,2,3]とある場合、[1],[2],[3],[1,2],[2,3][1,2,3] ([1,3]は要素が隣り合っていないので除外)を全て和を出して、最も大きな値を出す...

といった形で実現ができそうですが、やはりスマートではないですよね...

そこで、[1,2,3]とある場合、まず、2に着目し、前の要素と足し合わせます。

そして、それを2の位置に保存します。

そして今度は3に着目し、前の要素と足し合わせます。

すると、この配列は自然と...nums[0] ~ nums[1], nums[0] ~ nms[2]の和になっているのがわかるかと思います。

最終的に出来上がった配列の中の最も大きな値が自然と答えになる感じですね!

こんなイメージです。

ただ、一点注意が必要なのが、マイナスを含む場合です。

-3に着目して足すと...[1, -2, 2, 1],

2に着目して足すと....[1, -2, 0, 1],

1に着目して足すと...[1, -2, 0, 1]本来は nums[2] ~ nums[3]の3が答えになるべきですが、最大の値は1になっています。

これがどう言うことかと言うと、着目した値に対して、−の値になる場合は、それ以上伝播させないようにする必要があります。

今回ならば2に着目して-2を足しましたが、それは隣り合う要素の和を出す上で、最も大きな値を出したいのに、マイナスになっている時点でおかしい...と言うわけですね。

ちょっと難しいですが...

そのため、除外すべきです。

また...

逆に...

このように、前方から計算を繰り返し、正の数であれば、ただひたすら足していく（場合によっては間にマイナスがあるかもしれないが)と、負になったら、それ以降には伝播させないよう、そこで打ち止めし、次の要素同志から足し合わせ始める...といった具合に進めていくとうまくいきます。

では、最後に提出コードを貼っておきます。

提出コード

Runtime: 68 ms, faster than 52.56% of Python3 online submissions for Maximum Subarray.
Memory Usage: 15.2 MB, less than 14.96% of Python3 online submissions for Maximum Subarray.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # numsに隣あう要素の和を足し合わせていく
        for i in range(1, len(nums)):
            # 前の要素or和が正の場合のみ要素に足し合わせる
            if nums[i-1] > 0:
                nums[i] += nums[i-1]
        return max(nums)