Leetcode刷題記錄——53. 最大子序和

待補充：

分治法

0721 字首和On

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if nums == []:
            return 0
        pre = []#字首和list 先填一個0
        minpre = None#minpre[i]的含義是 [:i-1]中pre的最小值
        maxres = None
        for i,val in enumerate(nums):
            #print(i,val,minpre,maxres,pre)
            if pre == []:
                pre.append(val)
                minpre = min(0,val)
                maxres = val
            else:
                this_pre = val + pre[-1]
                pre.append(this_pre)
                maxres = max(maxres,this_pre-minpre)
                minpre = min(minpre,this_pre)
        return maxres

           

我實作的方法 複雜度為O(n)的動态規劃算法

其中，值得注意的是，

子問題f(i)的定義為以第i個數字(a[i])為結尾的最大和連續子數組的和

由于這個數組一定與a[i-1]連續，則也一定與以a[i-1]為結尾的最大和連續子數組相鄰

是以 狀态轉移方程滿足

f(i) = f(i-1) + a[i] if f(i-1) > 0 else a[i],i>=1

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if nums == []:
            return 0
        length = len(nums)
        if length == 1:
            return nums[0]
        #本解法中，動态規劃的狀态轉移方程f(i)
        #代表以a(i)為結尾的最大和連續子數組
        res = nums[0]
        maxa = res
        for i in range(length-1):
            tempindex = i + 1#nums[tempindex]代表新考察的數字
            if res >= 0:
                res += nums[tempindex]
            elif res < 0:
                res = nums[tempindex]
            if res > maxa:
                maxa = res
            

        return maxa