【问题描述】
给定一个整数数组 a[ ] ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
这个问题也可转入Leecode 51.最大子序和
来源：力扣（LeetCode）
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
以下用四种方法实现
①蛮力法（即暴力算法）实现：
代码实现：
int maxSubSum1(int a[],int n){
int i,j,k;
int maxSum=0,thisSum;
for(i=0;i<n;i++){
for(j=i;j<n;j++){
thisSum=0;
for(k=i;k<=j;k++)
thisSum+=a[k];
if(thisSum>maxSum)
maxSum=thisSum;
}
}
return maxSum;
}
算法复杂度T(n)=O(n^3)
解法2：
改进前面的解法，在求两个相邻子序列和的时候，它们之间是关联的。
例如a[0…3]子序列和=a[0]+a[1]+a[2]+a[3],a[0…4]子序列和=a[0]+a[1]+a[2]+a[3]+a[4]
在前者计算出来后，求后者时只需在前者的基础上加上a[4]即可，没有必须每次都重复计算。
从而提高算法效率。
代码实现：
int maxSbuSum2(int a[],int n) {
int i,j;
int maxSum=0,thisSum;
for(i=0;i<n;i++){
thisSum=0;
for(j=i;i<n;j++){
thisSum+=a[i];
if(thisSum>maxSum)
maxSum=thisSum;
}
}
return maxSum;
}
时间复杂度T(n)=O(n^2)
解法3：更进一步改进解法2
如果扫描中遇到了负数，当前子序列和thisSum将会减小，若thisSum为负数，表明
前面已经扫描的那个子序列可以抛弃了，则放弃这个子序列，重新开始下一个子序
列的分析，并置thisSum为0
若这个子序列和thisSum不断增加，那么最大子序列和maxSumy也不断增加。
int maxSubSum(int a[],int n){
int j,maxSum=0,thisSum=0;
for(j=0;j<n;j++){
thisSum+=a[j];
if(thisSum<0)
thisSum=0;
if(maxSum<thisSum)
maxSum=thisSum;
}
return maxSum;
}
②分治算法实现
【问题求解】
对于含有n个整数的序列a[0…n-1]，若n=1，表示该序列只含有1个元素，如果该元素大于0，则反汇该元素，否则返回0.
若n>1，采用分治法求解最大连续子序列时取其中中间位置mid=(n-1)/2向下取整，该子序列只可能出现在3个地方如下图所示
（1）该子序列完全在左半部分即a[0…mid]中采用递归求其最大连续子序列和maxLeftSum.
（2）该子序列完全落在右半部分，即a[mid+1…n-1]中，采用递归求出其最大连续子序列和maxRightSum
(3)该子序列跨越序列a的中部而占据左、右两部分。
代码实现：
#include<stdio.h>
int n=6;
int a[]={0,-2,11,-4,13,-5,-2};
int max(long a,long b,long c){ //求出a,b,c三者中的最大值
if(a<b) a=b;
if(a>c) return a;
else return c;
}
int maxSubArray(int left,int right)
{
int i,j;
int maxLeftSum,maxRightSum;
int maxLeftBorderSum,leftBorderSum;
int maxRightBorderSum,rightBorderSum;
if(left==right){ //当子序列只有一个元素时
if(a[left]>0) //元素大于0的时候返回它
return a[left];
else return 0; //小于或等于0的时候返回0
}
int mid=(left+right)/2;
maxLeftSum=maxSubArray(left,mid); //求左边的最大连续子序列的和
maxRightSum=maxSubArray(mid+1,right); //求右边的最大连续子序列之和
maxLeftBorderSum=0,leftBorderSum=0;
for(i=mid;i>=left;i--){ //求出以左边加上a[mid]元素构成的序列的最大和
leftBorderSum+=a[i];
if(leftBorderSum>maxLeftBorderSum)
maxLeftBorderSum=leftBorderSum;
}
maxRightBorderSum=0,rightBorderSum=0;
for(j=mid+1;j<=right;j++){ //求出a[mid]右边元素构成的序列的最大和
rightBorderSum+=a[j];
if(rightBorderSum>maxRightBorderSum)
maxRightBorderSum=rightBorderSum;
}
return max(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum);
}
int main(){
printf("%d",maxSubArray(0,n));
return 0;
}
③动态规划算法实现：
dp[i]表示数组a中以a[i]结尾的最大子序列和
状态转移方程如下
dp[0]=0 （边界条件）
dp[i]=max{dp[i-1]+ai,ai} (1<=i<=n)
即dp[i]要么是当前数字要不然是与前面的最大子序和的和。
代码实现：
#include<iostream>
#include<algorithm>
using namespace std;
int dp[100];
int n=6;
int a[]={0,-2,11,-4,13,-5,-2};
int Maxsum() //求解算法
{
int result=INT_MIN;
dp[0]=0;
result=dp[0];
for(int j=1;j<=n;j++){
dp[j]=max(dp[j-1]+a[j],a[j]);
result=max(result,dp[j]);
}
return result;
}
int main(){
cout<<Maxsum()<<endl;
return 0;
}
④贪心算法实现：
对素组从左向右迭代，一个个数字加过去，如果sum<0,重新开始找子序列。
代码实现：
#include<iostream>
#include<algorithm>
using namespace std;
int n=6;
int a[]={0,-2,11,-4,13,-5,-2};
int maxSubArray()
{
//因为int占4字节32位，根据二进制编码的规则，INT_MAX = 2^31-1，INT_MIN= -2^31.
//C/C++中，所有超过该限值的数，都会出现溢出，出现warning，但是并不会出现error
//INT_MAX = 2^31 - 1 =2147483647，INT_MIN= - 2^31 = -2147483648
int result = INT_MIN;
int sum = 0;
for (int i = 0; i <=n; i++)
{
sum += a[i];
result = max(result, sum);
//如果sum < 0，重新开始找序列
if (sum < 0)
{
sum = 0;
}
}
return result;
}
int main(){
cout<<maxSubArray()<<endl;
return 0;
}