LeetCode 53. Maximum Subarray

LeetCode 53. Maximum Subarray

LINK: https://leetcode.com/problems/maximum-subarray/

Matter

You are given an integer array.

Your task is to find a contiguous part of the array whose total sum is as large as possible, and return that maximum sum.

Example.

[1] Input:
nums = [-2,1,-3,4,-1,2,1,-5,4]

Output:
6

Explanation:
The subarray [4,-1,2,1] produces the largest sum, which is 6.

[2] Input:
nums = [1]

Output:
1

Explanation:
The only possible subarray is [1], so the answer is 1.

[3] Input:
nums = [5,4,-1,7,8]

Output:
23

Explanation:
Using the entire array gives the maximum total, 23.

Constraints

1 <= nums.length <= $10^5$

-$10^4$ <= nums[i] <= $10^4$

Problem analysis

A brute-force method would check every possible subarray and calculate its sum. That approach is too slow because there are too many combinations.

If the current running sum becomes negative, it is better to start fresh from the current element.

Because a negative prefix only reduces the value of any future subarray.

Solution

class Solution 
{
public:
    int maxSubArray(std::vector<int>& nums) 
    {
        int i32Cur = nums[0];
        int i32Max = nums[0];

        for (int i = 1; i < (int)nums.size(); i++)
         {
            i32Cur = std::max(nums[i], i32Cur + nums[i]);
            i32Max = std::max(i32Max, i32Cur);
        }

        return i32Max;
    }
};