最大子序和，又貪心又DP
從本題開始，貪心題目都比較難了!
最大子序和
力扣題目鏈接：https://leetcode-cn.com/problems/maximum-subarray
給定一個(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。
暴力解法
暴力解法的思路，第一層for 就是設(shè)置起始位置，第二層for循環(huán)遍歷數(shù)組尋找最大值
時(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 在一起，計(jì)算起點(diǎn)的時(shí)候，一定是從1開始計(jì)算，因?yàn)樨?fù)數(shù)只會(huì)拉低總和，這就是貪心貪的地方!
局部最優(yōu)：當(dāng)前“連續(xù)和”為負(fù)數(shù)的時(shí)候立刻放棄，從下一個(gè)元素重新計(jì)算“連續(xù)和”，因?yàn)樨?fù)數(shù)加上下一個(gè)元素 “連續(xù)和”只會(huì)越來越小。
全局最優(yōu)：選取最大“連續(xù)和”
局部最優(yōu)的情況下，并記錄最大的“連續(xù)和”，可以推出全局最優(yōu)。
從代碼角度上來講：遍歷nums，從頭開始用count累積，如果count一旦加上nums[i]變?yōu)樨?fù)數(shù)，那么就應(yīng)該從nums[i+1]開始從0累積count了，因?yàn)橐呀?jīng)變?yōu)樨?fù)數(shù)的count，只會(huì)拖累總和。
這相當(dāng)于是暴力解法中的不斷調(diào)整最大子序和區(qū)間的起始位置。
那有同學(xué)問了，區(qū)間終止位置不用調(diào)整么?如何才能得到最大“連續(xù)和”呢?
區(qū)間的終止位置，其實(shí)就是如果count取到最大值了，及時(shí)記錄下來了。例如如下代碼：
- if (count > result) result = count;
這樣相當(dāng)于是用result記錄最大子序和區(qū)間和(變相的算是調(diào)整了終止位置)。
如動(dòng)畫所示：
最大子序和
紅色的起始位置就是貪心每次取count為正數(shù)的時(shí)候，開始一個(gè)區(qū)間的統(tǒng)計(jì)。
那么不難寫出如下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ū)間累計(jì)的最大值（相當(dāng)于不斷確定最大子序終止位置）
- result = count;
- }
- if (count <= 0) count = 0; // 相當(dāng)于重置最大子序起始位置，因?yàn)橛龅截?fù)數(shù)一定是拉低總和
- }
- return result;
- }
- };
時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(1)
當(dāng)然題目沒有說如果數(shù)組為空，應(yīng)該返回什么，所以數(shù)組為空的話返回啥都可以了。
不少同學(xué)認(rèn)為 如果輸入用例都是-1，或者 都是負(fù)數(shù)，這個(gè)貪心算法跑出來的結(jié)果是0， 這是又一次證明腦洞模擬不靠譜的經(jīng)典案例，建議大家把代碼運(yùn)行一下試一試，就知道了，也會(huì)理解 為什么 result 要初始化為最小負(fù)數(shù)了。
動(dòng)態(tài)規(guī)劃
當(dāng)然本題還可以用動(dòng)態(tài)規(guī)劃來做，當(dāng)前「代碼隨想錄」主要講解貪心系列，后續(xù)到動(dòng)態(tài)規(guī)劃系列的時(shí)候會(huì)詳細(xì)講解本題的dp方法。
那么先給出我的dp代碼如下，有時(shí)間的錄友可以提前做一做：
- 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;
- }
- };
時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(n)
總結(jié)
本題的貪心思路其實(shí)并不好想，這也進(jìn)一步驗(yàn)證了，別看貪心理論很直白，有時(shí)候看似是常識(shí)，但貪心的題目一點(diǎn)都不簡(jiǎ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ū)間累計(jì)的最大值（相當(dāng)于不斷確定最大子序終止位置）
- if (count <= 0){
- count = 0; // 相當(dāng)于重置最大子序起始位置，因?yàn)橛龅截?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
- }
