Skip to content

Latest commit

 

History

History
216 lines (175 loc) · 7.33 KB

README.md

File metadata and controls

216 lines (175 loc) · 7.33 KB

53. Maximum Subarray (Easy)

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

A subarray is a contiguous part of an array.

 

Example 1:

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

Example 2:

Input: nums = [1]
Output: 1

Example 3:

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

 

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

 

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.

Companies:
LinkedIn, Amazon, Apple, Adobe, Microsoft, Google, Bloomberg, Cisco, Uber, eBay, Intel, Oracle, Walmart Labs, Facebook, Yahoo, Goldman Sachs, JPMorgan, ServiceNow, Shopee

Related Topics:
Array, Divide and Conquer, Dynamic Programming

Similar Questions:

Solution 1. Rolling Sum + Greedy

We can first get the rolling sum so that sum[i] = nums[0] + ... + nums[i]. With partial_sum we can do that in place.

Then this problem is almost the same as 121. Best Time to Buy and Sell Stock -- finding the maximum sum[j] - sum[i] where j > i. The only difference is that the sub array can start at index 0, so we also need to take sum[i] where 0 <= i < N into consideration. So the "minimum sum we've seen so far" should be initialized as 0.

// OJ: https://leetcode.com/problems/maximum-subarray/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        partial_sum(nums.begin(), nums.end(), nums.begin());
        int minSum = 0, ans = INT_MIN;
        for (int n : nums) {
            ans = max(ans, n - minSum);
            minSum = min(minSum, n);
        }
        return ans;
    }
};

Or

// OJ: https://leetcode.com/problems/maximum-subarray/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int maxSubArray(vector<int>& A) {
        int mn = 0, sum = 0, ans = INT_MIN;
        for (int n : A) {
            sum += n;
            ans = max(ans, sum - mn);
            mn = min(mn, sum);
        }
        return ans;
    }
};

Solution 2. DP

Let dp[i + 1] be the sum of maximum subarray ending with nums[i].

dp[i + 1] = max{
                dp[i] + A[i],   if dp[i] > 0
                A[i]            if dp[i] <= 0
            }

Or

dp[i + 1] = max(dp[i], 0) + A[i]

Where 0 <= i < N. Note that we can set dp[0] = 0 so that the equation stay true for i = 0.

The result is max{ dp[1], ..., dp[N] }.

// OJ: https://leetcode.com/problems/maximum-subarray/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = INT_MIN, N = nums.size();
        vector<int> dp(N + 1, 0);
        for (int i = 0; i < N; ++i) ans = max(ans, dp[i + 1] = max(dp[i], 0) + nums[i]);
        return ans;
    }
};

Solution 3. DP

We can optimize Solution 2 by storing dp in nums so that the space complexity is reduced from O(N) to O(1).

// OJ: https://leetcode.com/problems/maximum-subarray/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            nums[i] += max(nums[i - 1], 0);
            ans = max(ans, nums[i]);
        }
        return ans;
    }
};

Solution 4. DP

What if we are not allowed th change the value in nums array?

Since dp[i+1] is only dependent on dp[i], we can use O(1) space to store dp array -- only store the last value.

So we put the maximum subarray sum we've seen thus far into the cur variable. When we need to update cur for the current nums[i], we can simply do cur = max(cur, 0) + n.

// OJ: https://leetcode.com/problems/maximum-subarray/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = INT_MIN, cur = INT_MIN;
        for (int n : nums) {
            cur = max(cur, 0) + n;
            ans = max(ans, cur);
        }
        return ans;
    }
};

Solution 5. Divide and Conquer

See details here

// OJ: https://leetcode.com/problems/maximum-subarray/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(logN)
class Solution {
private:
    int crossSum(vector<int>& nums, int L, int R, int p) {
        if (L == R) return nums[L];
        int left = INT_MIN, right = INT_MIN, i, sum;
        for (i = p, sum = 0; i >= L; --i) left = max(left, sum += nums[i]);
        for (i = p + 1, sum = 0; i <= R; ++i) right = max(right, sum += nums[i]);
        return left + right;
    }
    
    int helper(vector<int>& nums, int L, int R) {
        if (L == R) return nums[L];
        int p = (L + R) / 2;
        int left = helper(nums, L, p);
        int right = helper(nums, p + 1, R);
        int cross = crossSum(nums, L, R, p);
        return max(left, max(right, cross));
    }
public:
    int maxSubArray(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }
};