Given an array of integers, find a contiguous subarray which has the largest sum.
Notice
The subarray should contain at least one number.
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)); } };
本文转自博客园Grandyang的博客，原文链接：最大子数组Maximum Subarray ，如需转载请自行联系原博主。
