Closed1

分割統治方 Divide and Conquer苦手なので

esakaesaka

ちょっと簡単な問題ときつつ
https://leetcode.com/problems/maximum-subarray/

LeetCodeの配列の中の部分配列の和で最大値となる問題を解く方法
思いついたのは、単純に前から見ていって、0下回ったらそこからまた和を再計算していく方法(0下回った時点で、その部分列必要ないため)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        tsum = 0
        ans = nums[0]
        for i in range(len(nums)):
            tsum += nums[i]
            ans = max(ans, tsum)
            if tsum < 0:
                tsum = 0
        return ans

分割統治でも解けるらしい

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        return self.findMaximumSubarray(nums, 0, len(nums)-1)
    
    def findMaximumSubarray(self, nums, l, r):
        # empty array
        if l > r:
            return -math.inf
        
        mid = (l + r) // 2 
        curr = lsum = rsum = 0
        
        for i in range(mid - 1, l - 1, -1):
            curr += nums[i]
            lsum = max(lsum, curr)
            
        curr = 0
        for i in range(mid + 1, r + 1):
            curr += nums[i]
            rsum = max(rsum, curr)            
        
        # ここで左右どっちも-で、midもマイナスだとしても、-値のマックス値が生まれる可能性がある(0マックスにならない)
        mixsum = nums[mid] + lsum + rsum
        
        lremain = self.findMaximumSubarray(nums, l, mid - 1)
        rremain = self.findMaximumSubarray(nums, mid + 1, r)
        
        return max(mixsum, lremain, rremain)

配列の真ん中と、その左右の部分列に分ける
左の部分列の和と右の部分列の和の瞬間最大値をとる(マイナスにならないように初期値0からで)
その後に、真ん中とそれぞれの部分列の和を足す。で答えの候補より大きかったら更新
終わったら、さらに左右の部分列を1つの列と見做して、再帰的に実施する

このスクラップは2022/01/19にクローズされました