【LeetCode】53. Maximum Subarrayを解く

問題へのリンク

問題概要

整数からなる配列numsが与えられる．
このとき，最低1つの数を含む隣接した部分配列の和が最大となるときの和の値を答える．

例：

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

制約

• $1 \leq nums.length \leq 3*10^4$
• $-10^5 \leq nums[i] \leq 10^5$

考えたこと

最初に思い付いたのは，二つのインデクスi, jを用意して，部分配列nums[i:j]の総和を総当たりすることで解を得る方法だ：

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        res = nums[0]
        for i in range(n):
            for j in range(i,n):
                res = max(res, sum(nums[i:j+1]))
        return res

ただし，この解法は時間計算量が$O(n^2)$となり計算時間超過となってしまう．

従って，何かしらの工夫をして計算量を減らす必要が出てくる．

$O(n)$の計算量で解を得ることを考えると，numsのインデクスiにおける最大の部分和を前から順に求めていき，前の解を利用して次のインデクスi+1の解を求めるという方法を考えた．

nums = [-2,1,-3,4,-1,2,1,-5,4]

1. [-2] -> -2
2. [-2,1] -> 1 (max(-2, 1, -2+1) = 1)
3. [-2,1,-3] -> 1 (max(1, -3, -3+1))
4. [-2,1,-3,4] -> 4 (max(1, 4, 4+1)) ??

実際にシミュレーションしてみると，この状況では前の解を利用しにくいことに気づく．
なぜなら，前のインデクスの要素が必ず利用されているとは限らず，利用されていない場合にはインデクスi+1の要素を含む部分配列を作れないからである．

ここで，

インデクスiを部分配列の最後の要素として持つ場合の最大和

という条件を付け足す．
このとき部分配列は必ず$1 \leq i \leq n$のインデクスを最後に持つため，一般性は失われない．

以上の条件でシミュレーションをしてみると以下のようになる：

nums = [-2,1,-3,4,-1,2,1,-5,4]

1. [-2] -> -2
2. [-2,1] -> 1 (max(1, -2+1))
3. [-2,1,-3] -> -2 (max(-3, -3+1))
4. [-2,1,-3,4] -> 4 (max(4, (-3+1)+4))
5. [-2,1,-3,4,-1] -> 3 (max(-1, 4-1))
6. [-2,1,-3,4,-1,2] -> 5 (max(2, (4-1)+2))
7. [-2,1,-3,4,-1,2,1] -> 6 (max(1, (4-1+2)+1))
8. [-2,1,-3,4,-1,2,1,-5] -> 1 (max(-5, (4-1+2+1)-5))
9. [-2,1,-3,4,-1,2,1,-5,4] -> 5 (max(4, (4-1+2+1-5)+4))

以上から，1~9のうち最大の値である6が解となる．

これは，カダネのアルゴリズム（Kadane's Algorithm）と言われている．

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = nums[0]
        for i in range(1,len(nums)):
            nums[i] = max(nums[i-1]+nums[i], nums[i])
            res = max(res, nums[i])
        return res