Question
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.
Difficulty:Easy
Category:Array, Divide-and-Conquer, Dynamic-Programming
Analyze
这道题目是求解最大的连续子序列和,依次处理每个元素:
- 如果当前元素加上之前的和 < 这个元素本身的数值, 那么就取这个元素本身的数值作为临时值
- 如果得到的临时数值比之前的最大值还要大,那么就替换这个数值
解决方案:如Solution1
Solution
Time complexity: O(n), Space Complexity: O(1)
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans = INT_MIN, temp = 0;
for (int& num : nums) {
temp = max(temp + num, num);
ans = max(temp, ans);
}
return ans;
}
};
Solution 2: Divide and Conquer
Cite: Maximum Subarray 最大子数组
题目还要求我们用分治法Divide and Conquer Approach来解,这个分治法的思想就类似于二分搜索法,我们需要把数组一分为二,分别找出左边和右边的最大子数组之和,然后还要从中间开始向左右分别扫描,求出的最大值分别和左右两边得出的最大值相比较取最大的那一个
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.empty()) return 0;
return helper(nums, 0, (int)nums.size() - 1);
}
int helper(vector<int>& nums, int left, int right) {
if (left >= right) return nums[left];
int mid = left + (right - left) / 2;
int lmax = helper(nums, left, mid - 1);
int rmax = helper(nums, mid + 1, right);
int mmax = nums[mid], t = mmax;
for (int i = mid - 1; i >= left; --i) {
t += nums[i];
mmax = max(mmax, t);
}
t = mmax;
for (int i = mid + 1; i <= right; ++i) {
t += nums[i];
mmax = max(mmax, t);
}
return max(mmax, max(lmax, rmax));
}
};