[LeetCode] 0053 Maximum Subarray

Maximum Subarray

LeetCode - 0053 Maximum Subarray
https://leetcode.com/problems/maximum-subarray/

Problem Description

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

Example:

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

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.

Solution

Dynamic Programming

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty()) return 0;
        int currMaxSum = nums[0];
        int maxSumSoFar = nums[0];
        for(int i = 1; i < nums.size(); i++){
            currMaxSum = std::max(currMaxSum+nums[i], nums[i]);
            maxSumSoFar = std::max(maxSumSoFar, currMaxSum);
        }
        return maxSumSoFar;
    }
};

Another way is to use std::max_element:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty()) return 0;
        for(int i = 1; i < nums.size(); i++)
            nums[i] = std::max(nums[i], nums[i]+nums[i-1]);

        return *std::max_element(std::begin(nums), std::end(nums));
    }
};

• Time complexity: O(n)
• Space complexity: O(1)