最大部分列和をKadane’s algorithmで解く

与えられた配列のうち、連続した部分配列の和の最大値を求める問題を考える（最大部分配列問題、最大部分列和問題）。

愚直に解くと二重ループだが、O(n^2)となり遅い。

DPの一種であるKadane’s algorithmを使うとO(n)で高速に解けるようになる。

試しにLeetCodeの53. Maximum Subarrayを解いてみる。

愚直解：O(n^2)

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

        ans = -1e5
        for i in range(n):
            for j in range(n):
                if j < i:
                    continue
                    
                temp = nums[i:j+1]
                ans = max(ans, sum(temp))
        
        return ans

Kadane’s algorithm O(n)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        best = -1e9
        cur = 0
        
        for i in range(len(nums)):
            cur = max(nums[i], nums[i] + cur)
            best = max(best, cur)
        
        return best

参考

Just a moment...

Maximum subarray problem - Wikipedia

Kadane’s Algorithm — (Dynamic Programming) — How and Why does it Work?

If you are here, then chances are that you were trying to solve the “Maximum Subarray Problem” and came across Kadane’s ...