53. Maximum Subarray

Posted on Edited on In

53. Maximum Subarray

Description

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

Example 1:

1
2
3
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:

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

Example 3:

1
2
3
Input: nums = [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.

Hints/Notes

Solution

Language: C++

preSum:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int preSum = 0, min_presum = 0, res = INT_MIN;
        for (auto& num : nums) {
            preSum += num;
            res = max(res, preSum - min_presum);
            min_presum = min(preSum, min_presum);
        }
        return res;
    }
};

dp:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(0, dp[i - 1]) + nums[i];
        }
        return ranges::max(dp);
    }
};