【题目】
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.
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
【分析】
【代码】
/*********************************
* 日期：2015-01-27
* 作者：SJF0115
* 题目: 53.Maximum Subarray
* 网址：https://oj.leetcode.com/problems/maximum-subarray/
* 结果：AC
* 来源：LeetCode
* 博客：
**********************************/
#include <iostream>
#include <climits>
using namespace std;
class Solution {
public:
int maxSubArray(int A[], int n) {
if(n <= 0){
return 0;
}//if
// 最大和
int max = A[0];
// 当前最大和
int cur = 0;
for(int i = 0;i < n;++i){
// 一旦当前最大和小于0就重置为0,一个负数只能使最大和变小
if(cur < 0){
cur = 0;
}//if
cur += A[i];
if(cur > max){
max = cur;
}//if
}//for
return max;
}
};
int main(){
Solution solution;
int n = 9;
int A[] = {-2,1,-3,4,-1,2,1,-5,4};
int result = solution.maxSubArray(A,n);
// 输出
cout<<result<<endl;
return 0;
}
【分析二】
如果将所给数组(A[0],...,A[n-1])分为长度相等的两段数组(A[0],...,A[n/2-1])和(A[n/2],...,A[n-1]),分别求出这两段数组各自最大子段和，
则原数组(A[0],...,A[n-1])的最大子段和分为以下三种情况，要么在前半部分a中，要么在后半部分b中，要么跨越a和b之间的边界：
a.(A[0],...,A[n-1])的最大子段和与(A[0],...,A[n/2-1])的最大子段和相同；
b.(A[0],...,A[n-1])的最大子段和与(A[n/2],...,A[n-1])的最大子段和相同；
c.(A[0],...,A[n-1])的最大子段跨过其中间两个元素A[n/2-1]到A[n/2]；
对应a和b两个问题是规模减半的两个相同的子问题，可以用递归求得。
对于c,需要找到以A[n/2-1]结尾的最大的一段连续数组之和S1=(A[i],...,A[n/2-1])和以A[n/2]开始的最大的一段连续数组之和S2=(A[n/2],...,A[j]),那么第三种情况的最大值为S1+S2。
只需要对原数组进行一次遍历即可。在a中的部分是a中包含右边界的最大子数组，在b中的部分是b中包含左边界的最大子数组。
这其实是一种分治策略，时间复杂度为O（nlogn）。
【代码二】
/*********************************
* 日期：2015-02-03
* 作者：SJF0115
* 题目: 53.Maximum Subarray
* 网址：https://oj.leetcode.com/problems/maximum-subarray/
* 结果：AC
* 来源：LeetCode
* 博客：
**********************************/
#include <iostream>
#include <climits>
using namespace std;
class Solution {
public:
int maxSubArray(int A[], int n) {
return Divide(A,0,n-1);
}
private:
int Divide(int A[],int left,int right){
if(left > right){
return 0;
}//if
if(left == right){
return A[left];
}//if
//
int mid = left + (right - left) / 2;
//1.跨越a和b之间的部分
//1.1在a中的部分是a中包含右边界的最大子数组
int sum = 0;
int leftMax = A[mid];
for(int i = mid;i >= left;--i){
sum += A[i];
leftMax = max(sum,leftMax);
}//for
//1.2在b中的部分是b中包含左边界的最大子数组
sum = 0;
int rightMax = A[mid+1];
for(int i = mid+1;i <= right;++i){
sum += A[i];
rightMax = max(sum,rightMax);
}//for
// 前半部分最大和
int aMax = Divide(A,left,mid);
// 后半部分最大和
int bMax = Divide(A,mid+1,right);
// 跨越mid的最大和
int cMax = leftMax + rightMax;
return max(max(aMax,bMax),cMax);
}
};
int main(){
Solution solution;
int n = 9;
int A[] = {-2,1,-3,4,-1,2,1,-5,4};
//int A[] = {-9,-2,-3,-5,-3};
//int A[] = {0,-2,3,5,-1,2};
int result = solution.maxSubArray(A,n);
// 输出
cout<<result<<endl;
return 0;
}
【分析三】
只遍历数组一遍，当从头到尾部遍历数组A， 遇到一个数有两种选择 （1）加入之前subArray （2）自己另起一个subArray
设状态S[i], 表示以A[i]结尾的最大连续子序列和，状态转移方程如下:
S[i] = max(S[i-1] + A[i],A[i])
时间复杂度：O(n) 空间复杂度：O(n)
【代码三】
/*--------------------------------------------
* 日期：2015-02-03
* 作者：SJF0115
* 题目: 53.Maximum Subarray
* 网址：https://oj.leetcode.com/problems/maximum-subarray/
* 结果：AC
* 来源：LeetCode
* 博客：
-----------------------------------------------*/
class Solution {
public:
int maxSubArray(int A[], int n) {
int S[n];
int maxSum = A[0];
S[0] = A[0];
// 动态规划
for(int i = 1;i < n;i++){
S[i] = max(S[i-1] + A[i],A[i]);
if(S[i] > maxSum){
maxSum = S[i];
}//if
}//for
return maxSum;
}
};
【解法四】
对前一个方法继续优化，从状态转移方程上S【i】只与S【i-1】有关，与其他都无关，因此可以用一个变量来记住前一个的最大连续数组和就可以了。
这样就可以节省空间了。
时间复杂度：O(n) 空间复杂度：O(1)
【代码四】
/*--------------------------------------------
* 日期：2015-02-03
* 作者：SJF0115
* 题目: 53.Maximum Subarray
* 网址：https://oj.leetcode.com/problems/maximum-subarray/
* 结果：AC
* 来源：LeetCode
* 博客：
-----------------------------------------------*/
class Solution {
public:
int maxSubArray(int A[], int n) {
int maxSum = A[0];
// sum 记住前一个的最大连续数组和
int sum = 0;
// 动态规划
for(int i = 0;i < n;i++){
sum += A[i];
sum = max(sum,A[i]);
if(sum > maxSum){
maxSum = sum;
}//if
}//for
return maxSum;
}
};
