LeetCode53 最大子序和

題目

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），傳回其最大和。

示例:

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

輸出: 6

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

進階:

如果你已經實作複雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/maximum-subarray

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

分析

做這題是因為當時算法課講到動态規劃，是以先做做動态規劃的簡單題。這題容易了解，但是我一直沒太懂哪裡用到了動态規劃。動态規劃不是先求解小問題，然後大問題利用小問題求得的解來繼續運算。直到求得問題的解

代碼

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum=0;
        int ans=nums[0];
        for(int i=0;i<nums.size();i++){
            if(sum>0){
                sum+=nums[i];
            }else{
                sum=nums[i];
            }
            ans=ans>sum?ans:sum;
        }
        return ans;
    }
};
           

再查詢别人的題解之後，摘取了一段别人的解釋，還不錯：

解題思路：

示例: [a, b , c, d , e]

解答這類題目, 省略不掉周遊, 是以我們先從周遊方式說起

通常我們周遊子串或者子序列有三種周遊方式

以某個節點為開頭的所有子序列: 如 [a]，[a, b]，[ a, b, c] … 再從以 b 為開頭的子序列開始周遊 [b] [b, c]。

根據子序列的長度為标杆，如先周遊出子序列長度為 1 的子序列，在周遊出長度為 2 的 等等。

以子序列的結束節點為基準，先周遊出以某個節點為結束的所有子序列，因為每個節點都可能會是子序列的結束節點，是以要周遊下整個序列，如: 以 b 為結束點的所有子序列: [a , b] [b] 以 c 為結束點的所有子序列: [a, b, c] [b, c] [ c ]。

第一種周遊方式通常用于暴力解法, 第二種周遊方式 leetcode (5. 最長回文子串 ) 中的解法就用到了。

第三種周遊方式 因為可以産生遞推關系, 采用動态規劃時, 經常通過此種周遊方式, 如 背包問題, 最大公共子串 , 這裡的動态規劃解法也是以 先周遊出 以某個節點為結束節點的所有子序列 的思路

對于剛接觸動态規劃的, 我感覺熟悉第三種周遊方式是需要抓住的核心

因為我們通常的慣性思維是以子序列的開頭為基準，先周遊出以 a 為開頭的所有子序列，再周遊出以 b 為開頭的…但是動态規劃為了找到不同子序列之間的遞推關系，恰恰是以子序列的結束點為基準的，這點開闊了我們的思路。

我在網上看不少解答時，直接閱讀其代碼，總是感覺很了解很吃力，因為好多沒有寫清楚，一些周遊到底代表什麼意思，看了許久仍不知是以然，下面的代碼中摘錄了 維基中的解釋，感覺比較清楚，供大家了解參考。

作者：lao-hu-8

連結：https://leetcode-cn.com/problems/maximum-subarray/solution/xiang-xi-jie-du-dong-tai-gui-hua-de-shi-xian-yi-li/

來源：力扣（LeetCode）

著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

動态規劃一般為了有遞推關系的分析，都是從末尾來遞推。感覺上面的代碼更像暴力法一些。

于是按照上面老哥的解釋，試着再重新寫一遍動态規劃的解題方法。

遞推關系為

sum[i] = max{sum[i-1]+a[i],a[i]}

代碼如下：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n=nums.size();
        int sum[n];
        sum[0]=nums[0];
        int ans=sum[0];
        for(int i=1;i<n;i++){
            sum[i]=sum[i-1]+nums[i]>nums[i]?sum[i-1]+nums[i]:nums[i];
            ans=sum[i]>ans?sum[i]:ans;
        }
        //找到其中最大的值
        return ans;
        
    }
};
           

上面兩個程式進行比較：兩者占用的記憶體空間差不多大，但是第二個程式的運作時間用了4ms，第一個用了8ms。第二個程式更快一些。了解第二個程式才能更好的了解此題使用動态規劃來解決問題。