leetcode with python:53. Maximum Subarray

题目:

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)
那我们下题见