一.問題描述

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

Example:

            
              Input:
            
             [-2,1,-3,4,-1,2,1,-5,4],

            
              Output:
            
             6

            
              Explanation:
            
            ?[4,-1,2,1] has the largest sum = 6.

          

Follow up:

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

二.解決思路

方法一：

首先建立一個新數組sumA

sumA[i]=a[0]+a[1]+...a[i-1]+a[i]=sumA[i-1]+nums[i]

然后一個子數組和最大相當于求max(sumA[i]-sumA[j], sumA[i])? i>j

如果sumA[j]是大于0的，我們就不用減去它

方法二：

考慮一下什么情況下會子數組最大和會從一個子數組變成另一個子數組

假設一開始的最大子數組是x1到y(tǒng)1

之后變成了x2到y(tǒng)2

分析可得知，這種變化只可能是x1到x2的和小于等于0的時候才成立（可以用反證法證明，很容易）

如果x1到x2的和不<0,那么x1到y(tǒng)2的和大于x2到y(tǒng)2的和

因此我們只需要迭代，當sum<0的時候，重新記錄sum，用res記錄最大

?

題目描述有提到用更高效的分治算法，后面看到會更新

更多l(xiāng)eetcode算法題解法請關注我的專欄leetcode算法從零到結束或關注我

歡迎大家一起套路一起刷題一起ac

三.源碼

            
              #method1
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums)==1:return nums[0]
        sumA=[]
        sumA.append(nums[0])
        max_sum,min_sum,rt=nums[0],nums[0],nums[0]
        for i in range(1,len(nums)):
            sumA.append(sumA[i-1]+nums[i])
            rt=max(rt,sumA[i],sumA[i]-min_sum)
            if sumA[i]
              
            
          

            
              #method2
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        rt=nums[0]
        sum_num=0
        for num in nums:
            if sum_num>=0:sum_num+=num
            else:sum_num=num
            rt=max(rt,sum_num)
        return rt
        
            
          

?