53. Maxmimum Subarray

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Array、Divide and Conquer、Dynamic Programming

一、題目

Given an integer array num, find the subarray with the largest sum, and return its sum.

Example 1:

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

Example 2:

  • Input: nums = [1]
  • Output: 1
  • Explanation: The subarray [1] has the largest sum 1.

Example 3:

  • Input: [5,4,-1,7,8]
  • Output: 23
  • Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

二、分析

  • 這題可以用動態規劃的思維下去解題，將 dp[i] 定為，到第 i 個數為止，最大子序列的總和。
  • 以上述的定義可以得到狀態轉移方程式：dp[i] = max(nums[i], nums[i] + dp[i-1]，對 i 元素來說，只需考慮兩種狀況：
    1. 前面的元素都不拿
    2. 拿包含前一個元素，且包含最大子序列的其它元素。

三、解題

1. DP

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(n)\)
int maxSubArray(vector<int>& nums) {
    int res = nums[0];
    // int curr = INT_MIN;
    vector<int> dp(nums.size(), 0);
    dp[0] = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        dp[i] = max(nums[i], nums[i] + dp[i-1]);
        res = max(dp[i], res);
    }
    return res;
}

2. DP(space optimized)

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(1)\)
int maxSubArray(vector<int>& nums) {
    int curr = INT_MIN, res = INT_MIN;
    for (const auto& x : nums) {
        curr = curr < 0 ? x : curr + x;
        res = max(res, curr);
    }
    return res;
}

回目錄 Catalog