[LeetCode Road] Maximum Subarray - Solution/C++

53. Maximum Subarray

Question:

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

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.

Example:

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

Input: nums = [1]
Output: 1

Input: nums = [0]
Output: 0

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

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

Constraints:

1 <= nums.length <= 2 * 10^4

-2^31 <= nums[i] <= 2^31 - 1

Source code

Version 1

Idea:
It is a brute force approach. Use 2 loop to calculate the sum for each elements.

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

Version 2

Idea:
This is an efficient method, use only one loop.
sum += nums[i] means the cumulative sum.
sum = max(sum, nums[i]) means the maximum of sum between the cumulative sum or current index of value.
maxValue = max(maxValue, sum) means recording the maximal value.

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