題目網址：https://leetcode.cn/problems/maximum-subarray/

題意：給一 array nums, 找到一 subarray, 其元素和為所有 subarray 中最大的。

注意：subarray 必須是連續的（index 不可中斷）

Solution 1：

想法：利用 DP, 每個元素都有加入 or 不加入 subarray 兩種選擇。若不加入, 則該元素成為新的 subarray 的開頭繼續往後尋找, 其中 dp[i] 代表 [0, i] 這個區間中擁有最大和的 subarray 之和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        const int n = nums.size();
        int res = nums[0];
        vector<int> dp(n, nums[0]);

        for (int i = 1; i < n; ++i) {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
            res = max(res, dp[i]);
        }

        return res;
    }
};
  • time：$O(n)$ ➔ 遍歷 nums 中的元素
  • space：$O(n)$ ➔ dp

Solution 2：

想法：改進 Solution 1, 由於 dp[i] 只需紀錄 dp[i - 1] 就好, 因此不需要開到 n 個空間

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = nums[0], cur = nums[0];

        for (int i = 1; i < nums.size(); ++i) {
            cur = max(nums[i], cur + nums[i]);
            res = max(res, cur);
        }

        return res;
    }
};
  • time：$O(n)$ ➔ 遍歷 nums
  • space：$O(1)$ ➔ 只需常數空間