Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
今天的題目是找相加和最大的連續子數組，題目難度為Medium。
這道題典型的解決辦法是Kadane's algorithm，不知道算法名無所謂，相信大家也能想到實現細節。逐個遍歷數組元素並將其加入累加和（sum），如果累加和大於記錄的最大和（maxSum），更新maxSum，如果sum小於等於0，表明之前的子數組不會提高後續數組的相加和，拋棄之前的子數組，將sum重新置為0，這樣遍歷數組即可得到maxSum。具體代碼：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum = 0, maxSum = INT_MIN;
for(int num:nums) {
sum += num;
maxSum = max(maxSum, sum);
if(sum < 0) sum = 0;
}
return maxSum;
}
};
如果要得到最大和子數組的起始和結束為止，可以用下面的方法：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum = 0, maxSum = INT_MIN;
int l = 0, r = 0, maxL = 0, maxR = 0;
for(int i=0; i<nums.size(); ++i) {
sum += nums[i];
if(sum > maxSum) {
maxSum = sum;
r = i;
maxL = l;
maxR = r;
}
if(sum < 0) {
sum = 0;
l = i + 1;
r = l;
}
}
return maxSum;
};
上面介紹的Kadane's algorithm不僅可以求連續子數組的最大和，還可以求最小和，方法是一樣的。
另外，題目要求用分治法解題，就再來個分治法的版本。對任意位置元素，如果該元素在最大和子數組內部，可以以該元素為中心向兩邊逐個加數組元素，判斷包含該元素在內部的子數組的最大和；如果該元素不在最大和子數組內部，可以在此元素位置將數組劃分為兩個獨立數組，分別求這兩個數組的連續子數組最大和，這樣就把問題通過分治法分割為了兩個相同的子問題，通過比較這三個最大和即可得到最終結果。具體代碼：
class Solution {
int getMaxSum(const vector<int>& nums, int bgn, int end) {
if(bgn == end) return nums[bgn];
int mid = (bgn + end) / 2;
int lMaxSum = INT_MIN, rMaxSum = INT_MIN, sum = 0;
for(int i=mid; i>=bgn; --i) {
sum += nums[i];
lMaxSum = max(lMaxSum, sum);
}
sum = 0;
for(int i=mid+1; i<=end; ++i) {
sum += nums[i];
rMaxSum = max(rMaxSum, sum);
}
int left = getMaxSum(nums, bgn, mid);
int right = getMaxSum(nums, mid+1, end);
return max(max(left, right), lMaxSum+rMaxSum);
}
public:
int maxSubArray(vector<int>& nums) {
if(nums.empty()) return 0;
return getMaxSum(nums, 0, nums.size()-1);
}
};