一.問題描述

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.

二.解決思路

方法一：

首先建立一個新數(shù)組sumA

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

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

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

方法二：

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

假設(shè)一開始的最大子數(shù)組是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算法題解法請關(guān)注我的專欄leetcode算法從零到結(jié)束或關(guān)注我

歡迎大家一起套路一起刷題一起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
        
            
          

?