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

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

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

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

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

Loading...
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

愚直解: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

参考

Loading...
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
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 Algorithm but…

コメント

タイトルとURLをコピーしました