[LintCode] Maximum Subarray 最大子数组

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 = 0;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 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));}
};