Skip to content

Maximum Subarray⚓︎

Link

Description⚓︎

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

A subarray is a contiguous non-empty sequence of elements within an array.

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: 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

Solution⚓︎

See reference (Chinese).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            res = max(res, sum);
            if (sum <= 0) sum = 0;
        }
        return res;
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(1)\).

Prefix Sum⚓︎

See reference (Chinese).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int minPrefixSum = 0, prefixSum = 0;

        for (int num : nums) {
            prefixSum += num;
            res = max(res, prefixSum - minPrefixSum);
            minPrefixSum = min(minPrefixSum, prefixSum);
        }
        return res;
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(1)\).

Dynamic Programming⚓︎

See reference (Chinese).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 0);
        dp[0] = nums[0];

        int res = dp[0];
        for (int i = 1; i < n; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(n)\).