第三天的題目 53. Maximum Subarray 是演算法課程中很經典的一個題型:給定一個數列後找出相加總和最大的連續子數列

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

初步想法是看前 n-1 個加上會不會讓自己變大,如果會就加,不會就從自己開始重算

static int __ = [](){ std::ios::sync_with_stdio(false); return 0;}();
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ret = nums[0];
        vector<int> max(nums.size());
        max[0] = nums[0];
        for(int i=1; i<nums.size(); i++) {
            if(nums[i] + max[i-1] < nums[i])
                max[i] = nums[i];
            else
                max[i] = nums[i] + max[i-1];
        }

        for(int i=0; i<max.size(); i++) {
            if(max[i] > ret)
                ret = max[i];
        }
        
        return ret;
    }
};

寫完整理一下想法,改進下面幾點
👉直接修改傳進來的 nums,不需要額外新增 array
👉兩個 for 可以直接合併,在同一輪就同步算出目前的最大值
👉精簡判斷寫法
 ① 改成?:一行解決
 ② 改判斷 num[n-1] 是正或負,因為負數加起來就會變小,所以正數再加就好

static int __ = [](){ std::ios::sync_with_stdio(false); return 0;}();

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ret = nums[0];
        for(int i=1; i<nums.size(); i++) {
            nums[i] += (nums[i-1] > 0 ? nums[i-1] : 0);
            ret = max(ret, nums[i]);
        }
        
        return ret;
    }
};

第三天結束,每天持續進步一點點 😛😛

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料