Maximum Subarray 最大子序和

今天的題目是 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.

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.

給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4],

輸出: 6

解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。

進(jìn)階:

如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

Solutions:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = nums[0]
        lst = 0
       # if(len(nums)==1): return nums[0]
       '''
       設(shè)置一個(gè)累加值，一個(gè)next_item值，一個(gè)max_sum值進(jìn)行比較。
       累加值是經(jīng)過(guò)的數(shù)值累加的結(jié)果，next_item指示循環(huán)中的下一個(gè)新值，
       max_sum用來(lái)保留全局最大，并做返回值。
       '''
        for next_item in nums:
            lst = max(next_item,lst+next_item)
            max_sum = max(max_sum,lst)

        return max_sum

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        '''
        用DP的思想來(lái)解，并對(duì)數(shù)組進(jìn)行原地修改，修改后的值等于該位置之前的最大累加和。
        nums[0]不變，從nums[1]開(kāi)始更新，對(duì)于i位置新值等于nums[i]和nums[i]+累加值
        nums[i-1]中最大項(xiàng)。如果nums[i]小于0則累加后數(shù)值變小,經(jīng)過(guò)max之后會(huì)被篩選掉。
        最后返回nums數(shù)組中的最大值即可。
        '''
        for i in range(1, len(nums)):
            nums[i] = max(nums[i], nums[i] + nums[i - 1])
        return max(nums)