題目:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

給定一個陣列,找出最大子陣列和

看到這題時我腦中沒有頭緒,一個小時後,依然沒有,只好硬著頭皮暴力解

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans=""
        for i in range(len(nums)):
            if ans=="":
                ans=nums[i]
            c=nums[i]
            if c>ans:
                ans=c
            for j in range(i+1,len(nums)):
                c=c+nums[j]
                if c>ans:
                    ans=c
        return ans

想當然耳,Time Limit Exceeded

於是打開related topics看到dynamic programming
也就是大名鼎鼎的動態規劃,上網查了一下定義,看到下面這句

動態規劃是分治法的延伸。當分治法分割出來的問題，一而再、再而三出現，就運用記憶法儲存這些問題的答案，避免重複求解，以空間換取時間。

但這句話對我寫出正解還是沒什麼太大的幫助,過了一個小時,還是翻了討論區QQ

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

看了一下大概了解這個解法的理念了
我們知道(負數＋x)一定< x
因此當知道前面一串子陣列和是負的時候我們就不用考量其他包含前面這串子陣列的可能了
因為我們要求的是最大子陣列和,而這些可能只要將前面負的這一part去除,就有更大的子陣列和了,因此不用考慮
舉例來說[-1,2,3]這個陣列與其考慮[-1,2],[-1,2,3]不如直接看[2],[2,3]
所以我們讓y從第一項開始加,但y一旦 < 0 就歸0重算
因為與其看y < 0 + 後面陣列元素的可能,不如直接歸0看沒有 y 的子陣列(因為y+子陣列和<子陣列和)
這樣我們的y就以O(n)遍歷了所有可能為最大子陣列和的可能
途中路過的最大y值就是我們要return的值,最大子陣列和
最後執行時間735ms(faster than 95.47%)

不過到這裡還沒結束,題目下面又寫了一句

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

要我們嘗試用分治法(divide and conquer)下去解,這裡我也沒有頭緒,甚至看了解答過一陣子才懂
這邊寫一下我查到的分治法定義:

把一個複雜的問題分成兩個或更多的相同或相似的子問題，直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合併。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def midsum(nums,l,r,mid):
            rsum=0
            lsum=0
            temp=0
            for i in range(mid-1,l-1,-1):
                temp=temp+nums[i]
                lsum=max(temp,lsum)
            temp=0
            for i in range(mid+1,r+1):
                temp=temp+nums[i]
                rsum=max(temp,rsum)
            return rsum+lsum+nums[mid]
        
        def maxsum(nums,l,r):
            if l>=r:
                return nums[l]
            
            mid=(l+r)//2
            lmax = maxsum(nums, l, mid-1)
            rmax = maxsum(nums, mid+1, r)
            cmax = midsum(nums,l,r,mid)
            return max(lmax,rmax,cmax)
        
        return maxsum(nums,0,len(nums)-1)

一個陣列的子陣列只有三種可能全在左邊,全在右邊跟路過中間
那我們題目要求的就是在這三種可能的最大值取最大值(max(lmax,rmax,cmax))
rmax就是右邊陣列的max(lmax,rmax,cmax),lmax就是左邊陣列的max(lmax,rmax,cmax)
因此我們過程中會將陣列不斷砍半,用分治法的概念,以遞迴去實作,不斷取max(lmax,rmax,cmax)
cmax則是設立中間值(mid),分別從mid左右往外加,過程記錄遍歷的最大值,最後cmax=max(lsum)+mid+max(rsum)
ex:[5(lsum=2),-7(lsum=-3),4(lsum=4),-1(mid),7(rsum=7),8(rsum=15),-5(rsum=10)]
cmax=max(lsum)+mid+max(rsum)=4+(-1)+15=18,即[4,-1,7,8]為有路過中間可能的最大值

接著我們以[5,4,-1,7,8]為例來演示一下程式的運行:

最後執行時間3674ms(faster than 5%)
比較慢,畢竟O(nlogn)還是不敵O(n)

這次是第一次在leetcode上遇到不會的題目,不過也學到不少東西
希望能充分吸收並在未來加以運用

本題學習到的重點:動態規劃(Dynamic Programming),分治法(Divide and Conquer)
那我們下題見