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. 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;
}