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.
算法一
O(n)，在leetcode上实际执行时间为16ms。
class Solution {
public:
int maxSubArray(int A[], int n) {
if (n <= 0) return INT_MIN;
int sum = A[0];
int maxSum = sum;
for (int i=1; i<n; i++) {
sum = max(A[i], sum+A[i]);
maxSum = max(maxSum, sum);
}
return maxSum;
}
};
算法二 divide and conquer
O(nlogn), 在leetcode上实际执行时间为18ms。
class Solution {
public:
int maxSubArray(int A[], int n) {
if (n <= 0) return INT_MIN;
return helper(A, 0, n-1);
}
int helper(int A[], int left, int right) {
if (left == right)
return A[left];
const int mid = left + (right-left) / 2;
int sum = A[mid];
int midMax = sum;
for (int i=mid-1; i>=left; i--) {
sum += A[i];
midMax = max(midMax, sum);
}
sum = midMax;
for (int i=mid+1; i<=right; i++) {
sum += A[i];
midMax = max(midMax, sum);
}
const int leftMax = helper(A, left, mid);
const int rightMax = helper(A, mid+1, right);
return max(midMax, max(leftMax, rightMax));
}
};
参考自：
https://oj.leetcode.com/discuss/694/how-solve-maximum-subarray-using-divide-and-conquer-approach