[[434714]]

從本題開始，貪心題目都比較難了!

 最大子序和

力扣題目鏈接：https://leetcode-cn.com/problems/maximum-subarray

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

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

暴力解法

暴力解法的思路，第一層for 就是設(shè)置起始位置，第二層for循環(huán)遍歷數(shù)組尋找最大值

時間復(fù)雜度：O(n^2) 空間復(fù)雜度：O(1)

class Solution { 
public: 
    int maxSubArray(vector<int>& nums) { 
        int result = INT32_MIN; 
        int count = 0; 
        for (int i = 0; i < nums.size(); i++) { // 設(shè)置起始位置 
            count = 0; 
            for (int j = i; j < nums.size(); j++) { // 每次從起始位置i開始遍歷尋找最大值 
                count += nums[j]; 
                result = count > result ? count : result; 
            } 
        } 
        return result; 
    } 
}; 

以上暴力的解法C++勉強(qiáng)可以過，其他語言就不確定了。

貪心解法

貪心貪的是哪里呢?

如果 -2 1 在一起，計算起點的時候，一定是從1開始計算，因為負(fù)數(shù)只會拉低總和，這就是貪心貪的地方!

局部最優(yōu)：當(dāng)前“連續(xù)和”為負(fù)數(shù)的時候立刻放棄，從下一個元素重新計算“連續(xù)和”，因為負(fù)數(shù)加上下一個元素 “連續(xù)和”只會越來越小。

全局最優(yōu)：選取最大“連續(xù)和”

局部最優(yōu)的情況下，并記錄最大的“連續(xù)和”，可以推出全局最優(yōu)。

從代碼角度上來講：遍歷nums，從頭開始用count累積，如果count一旦加上nums[i]變?yōu)樨?fù)數(shù)，那么就應(yīng)該從nums[i+1]開始從0累積count了，因為已經(jīng)變?yōu)樨?fù)數(shù)的count，只會拖累總和。

這相當(dāng)于是暴力解法中的不斷調(diào)整最大子序和區(qū)間的起始位置。

那有同學(xué)問了，區(qū)間終止位置不用調(diào)整么?如何才能得到最大“連續(xù)和”呢?

區(qū)間的終止位置，其實就是如果count取到最大值了，及時記錄下來了。例如如下代碼：

if (count > result) result = count; 

這樣相當(dāng)于是用result記錄最大子序和區(qū)間和(變相的算是調(diào)整了終止位置)。

如動畫所示：

最大子序和

紅色的起始位置就是貪心每次取count為正數(shù)的時候，開始一個區(qū)間的統(tǒng)計。

那么不難寫出如下C++代碼(關(guān)鍵地方已經(jīng)注釋)

class Solution { 
public: 
    int maxSubArray(vector<int>& nums) { 
        int result = INT32_MIN; 
        int count = 0; 
        for (int i = 0; i < nums.size(); i++) { 
            count += nums[i]; 
            if (count > result) { // 取區(qū)間累計的最大值（相當(dāng)于不斷確定最大子序終止位置） 
                result = count; 
            } 
            if (count <= 0) count = 0; // 相當(dāng)于重置最大子序起始位置，因為遇到負(fù)數(shù)一定是拉低總和 
        } 
        return result; 
    } 
}; 

時間復(fù)雜度：O(n) 空間復(fù)雜度：O(1)

當(dāng)然題目沒有說如果數(shù)組為空，應(yīng)該返回什么，所以數(shù)組為空的話返回啥都可以了。

不少同學(xué)認(rèn)為 如果輸入用例都是-1，或者 都是負(fù)數(shù)，這個貪心算法跑出來的結(jié)果是0， 這是又一次證明腦洞模擬不靠譜的經(jīng)典案例，建議大家把代碼運(yùn)行一下試一試，就知道了，也會理解 為什么 result 要初始化為最小負(fù)數(shù)了。

動態(tài)規(guī)劃

當(dāng)然本題還可以用動態(tài)規(guī)劃來做，當(dāng)前「代碼隨想錄」主要講解貪心系列，后續(xù)到動態(tài)規(guī)劃系列的時候會詳細(xì)講解本題的dp方法。

那么先給出我的dp代碼如下，有時間的錄友可以提前做一做：

class Solution { 
public: 
    int maxSubArray(vector<int>& nums) { 
        if (nums.size() == 0) return 0; 
        vector<int> dp(nums.size(), 0); // dp[i]表示包括i之前的最大連續(xù)子序列和 
        dp[0] = nums[0]; 
        int result = dp[0]; 
        for (int i = 1; i < nums.size(); i++) { 
            dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 狀態(tài)轉(zhuǎn)移公式 
            if (dp[i] > result) result = dp[i]; // result 保存dp[i]的最大值 
        } 
        return result; 
    } 
}; 

時間復(fù)雜度：O(n) 空間復(fù)雜度：O(n)

總結(jié)

本題的貪心思路其實并不好想，這也進(jìn)一步驗證了，別看貪心理論很直白，有時候看似是常識，但貪心的題目一點都不簡單!

后續(xù)將介紹的貪心題目都挺難的，哈哈，所以貪心很有意思，別小看貪心!

其他語言版本

Java

class Solution { 
    public int maxSubArray(int[] nums) { 
        if (nums.length == 1){ 
            return nums[0]; 
        } 
        int sum = Integer.MIN_VALUE; 
        int count = 0; 
        for (int i = 0; i < nums.length; i++){ 
            count += nums[i]; 
            sum = Math.max(sum, count); // 取區(qū)間累計的最大值（相當(dāng)于不斷確定最大子序終止位置） 
            if (count <= 0){ 
                count = 0; // 相當(dāng)于重置最大子序起始位置，因為遇到負(fù)數(shù)一定是拉低總和 
            } 
        } 
       return sum; 
    } 
} 

// DP 方法 
class Solution { 
    public int maxSubArray(int[] nums) { 
        int ans = Integer.MIN_VALUE; 
        int[] dp = new int[nums.length]; 
        dp[0] = nums[0]; 
        ans = dp[0]; 
 
        for (int i = 1; i < nums.length; i++){ 
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]); 
            ans = Math.max(dp[i], ans); 
        } 
 
        return ans; 
    } 
} 

Python

class Solution: 
    def maxSubArray(self, nums: List[int]) -> int: 
        result = -float('inf') 
        count = 0 
        for i in range(len(nums)): 
            count += nums[i] 
            if count > result: 
                result = count 
            if count <= 0: 
                count = 0 
        return result 

Go

func maxSubArray(nums []int) int { 
    maxSum := nums[0] 
    for i := 1; i < len(nums); i++ { 
        if nums[i] + nums[i-1] > nums[i] { 
            nums[i] += nums[i-1] 
        } 
        if nums[i] > maxSum { 
            maxSum = nums[i] 
        } 
    } 
    return maxSum 
}