動機

分治也是可以重複走的

暴力

就列舉

def mss(l):
  return max([[sum(l[i:j+1]) for j in range(0, len(l)-i)] for i in range(0,len(l))])

分治

分成

  • 只有左邊
  • 只有右邊
  • cross兩邊

兩邊怎麼算? 從中間延伸出去，再把兩邊加起來

原本認定分治的割出來的遞迴是不會重複走到之前其他遞迴走過的部分 但經過這個才想起來，merge sort也是都重複走了array log(n)次阿!!

def helper(l):
    if len(l) == 0:
        return 0
    ret = tmp = l[0]
    for n in l[1:]:
        tmp += n
        ret = max(ret, tmp)
    return ret
def mss(l: List[int]) -> int:
    if not l:
        return 0
    if len(l) == 1:
        return l[0]
    else:
        if len(l) % 2 == 0:
            mid = len(l) // 2
            onlyLeft = mss(l[:mid])
            onlyRight = mss(l[mid:])
            center = 0
            left = helper(l[:mid][::-1])
            right = helper(l[mid:])
        else:
            mid = len(l) // 2
            onlyLeft = mss(l[:mid+1])
            onlyRight = mss(l[mid:])
            center = l[mid]
            left = helper(l[:mid][::-1])
            right = helper(l[mid+1:])
    return max([center + left + right, onlyLeft, onlyRight])

DP

tmp紀錄定義為以此為終點的mss 之後就是看之前的加現在看哪個大

def mss(self, nums: List[int]) -> int:
    ret = tmp = nums[0]
    for n in nums[1:]:
        tmp = max(n, n+tmp)
        ret = max(ret, tmp)
    return ret

Ref

分治 P.S.:geeksforgeeks的資料會不會太贊了