Given an array of integers, find a contiguous subarray which has the largest sum.
Notice
The subarray should contain at least one number.
Have you met this question in a real interview?
Yes
Example
Given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.
Challenge
Can you do it in time complexity O(n)?
LeetCode上的原题，请参见我之前的博客Maximum Subarray。
解法一：
class Solution {
public:
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
int maxSubArray(vector<int> nums) {
int res = INT_MIN, curSum = ;
for (int num : nums) {
curSum += num;
curSum = max(curSum, num);
res = max(res, curSum);
}
return res;
}
};
解法二：
class Solution {
public:
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
int maxSubArray(vector<int> nums) {
if (nums.empty()) return ;
return helper(nums, , (int)nums.size() - );
}
int helper(vector<int>& nums, int left, int right) {
if (left >= right) return nums[left];
int mid = left + (right - left) / ;
int lmax = helper(nums, left, mid - );
int rmax = helper(nums, mid + , right);
int mmax = nums[mid], t = mmax;
for (int i = mid - ; i >= left; --i) {
t += nums[i];
mmax = max(mmax, t);
}
t = mmax;
for (int i = mid + ; i <= right; ++i) {
t += nums[i];
mmax = max(mmax, t);
}
return max(mmax, max(lmax, rmax));
}
};