Leetcode 150 — Kadane’s Algorithm 解題心得

Leetcode 150 — Kadane’s Algorithm 解題心得¶

基本題型是給定一個list，要去找list中subarray的最大值，subarray的定義是list中的連續片段

另一種變形體是一樣找最大subarray，但是可以頭尾互接(一樣需要遵守subarray的連續)

這種題型基本上，因為是要找最大值，所以我們只需要一個pointer，從起頭走到尾吧，並且持續加總，加總過程去比對當下值跟遇到的最大值(這樣可以確保把最大值保存)，再來是如果當下的加總是小於0，表示該pointer以前的加總會是負，直接不用看，等於當下值即可，程式碼如下

class Solution:    def maxSubArray(self, nums: List[int]) -> int:        res, cur = float('-inf'),0        r,N = 0,len(nums)        while r<N:            if cur<=0: cur=nums[r]                else: cur+=nums[r]            r+=1            res = max(res,cur)        return res

而可以迴圈的狀況，可以想像成我們是在找中間的最小值，用list sum去扣除最小的可能值，就表示抓到可以的最大值

程式碼如下:

class Solution:    def maxSubarraySumCircular(self, nums: List[int]) -> int:        nor_res,N = float("-inf"),len(nums)        l,cur =0,0        while l<N:            if cur<0: cur=nums[l]            else: cur+=nums[l]            l+=1            nor_res = max(nor_res, cur)        if N>=3:            l,cur=1,0            cur_min = float("inf")            while l<N-1:                if cur>=0: cur = nums[l]                else: cur+=nums[l]                l+=1                cur_min = min(cur_min, cur)            nor_res = max(nor_res, sum(nums)-cur_min)        return nor_res

Leetcode 150 — Kadane’s Algorithm 解題心得

Leetcode 150 — Kadane’s Algorithm 解題心得¶

Comments

Leave a Comment