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) {
        const int n = nums.size();
        int max_subarray_sum = numeric_limits<int>::min();
        for (int i = 0, sum = 0; i < n; ++i) {
            sum = nums[i] + max(0, sum);
            max_subarray_sum = max(sum, max_subarray_sum);
        }

        return max_subarray_sum;
    }
};