53. Maximum Subarray

1. Description

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

2. Example

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.

3. Constraints

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

4. Solutions

Kadane

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

class Solution {
public:
    int maxSubArray(const vector<int> &nums) {
        int sum = 0, max_sum = numeric_limits<int>::min();
        for (int num : nums) {
            sum = max(0, sum);
            sum += num;
            max_sum = max(max_sum, sum);
        }

        return max_sum;
    }
};