53. Maximum Subarray

1. Description

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

2. 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.

3. Example

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

Example 2:
Input: nums = [1]
Output: 1

Example 3:
Input: nums = [0]
Output: 0

Example 4:
Input: nums = [-1]
Output: -1

Example 5:
Input: nums = [-2147483647]
Output: -2147483647

4. Constraints

• 1 <= nums.length <= $2 * 10^4$
• $-2^{31}$ <= nums[i] <= $2^{31} - 1$

5. Solutions

Dynamic Programming

n = nums.size()
Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    int maxSubArray(const vector<int> &nums) {
        int max_sum = INT_MIN;
        for (int i = 0, sum = 0; i < nums.size(); ++i) {
            sum = nums[i] + max(sum, 0);
            max_sum = max(sum, max_sum);
        }

        return max_sum;
    }
};