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:
- Best Time to Buy and Sell Stock (Easy)
- Maximum Product Subarray (Medium)
- Degree of an Array (Easy)
- Longest Turbulent Subarray (Medium)
- Maximum Absolute Sum of Any Subarray (Medium)
- Maximum Subarray Sum After One Operation (Medium)
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;
}
};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;
}
};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;
}
};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;
}
};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);
}
};