最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

• 示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

分治法

• 思路：

  将原数组分成左右两部分，元素数都为n/2,令最大子数组的下标为i,j则i和j的情况分为三种：
  

  1. i，j都属于原数组的左半侧，即low<=i<=j<=mid
     
  2. i，j都属于原数组的有半侧，即mid<i<=j<=high
     
  3. i，j跨越mid点，即low<=i<=mid<j<=high
     

  则根据上述的三种情况建立分治策略，分别求解左侧部分的最大子数组、右侧部分的最大子数组和跨越mid的最大子数组，然后比较上述三个最大子数组取最大值，即为给定数组的最大子数组

• 伪码:

  //求解跨越mid的最大子数组//由于i，j跨越mid，则左侧的末尾元素一定是mid，右侧的起始元素一定是mid+1FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high)    //跨越mid左侧部分的最大值    left-sum=MIN //初始值为最小值    sum=0    max-left//存储下标    for i=mid to low        sum=A[i]+sum        if sum>left-sum            max-left=i            left-sum=sum    //跨越mid右侧部分的最大值    right-sum=MIN    sum=0    max-right    for j=mid+1 to high        sum=A[j]+sum        if sum>right-sum            max-right=j            right-sum=sum    return(max-left,max-right,left-sum+right-sum)//求数组A的最大子数组FIND-MAXIMUM-SUBARRAY(A,low,high)    if low==high        return(low,high,A[low])//只有一个元素的情况，返回当前元素的位置和值    else        mid=(low+high)/2        (left-low,left-high,left-sum)=FIND-MAXIMUM-SUBARRAY(A,low,mid)        (right-low,right-high,right-sum)=FIND-MAXIMUM-SUBARRAY(A,mid+1,high)        (corss-low,cross-high,cross-sum)=FIND-MAX-CROSSING-SUBARRAY(A,low,mid,high)        if left-sum>right-sum and left-sum>corss-sum            return (left-low,left-high,left-sum)        else if right-sum>left-sum and right-sum>corss-sum            return (right-low,right-high,right-sum)        else            return (cross-low,cross-high,cross-sum)

• 时间复杂度分析：求解跨越mid的最大子数组部分时间复杂度为(n),分解部分时间复杂度为常数，则T(n)=2T(n/2)+(n),即T(n)=(nlgn)

• 源码实现：

  #include <iostream>#include <tuple>#include <limits.h>using namespace std;typedef tuple<int,int,long long> resultType;resultType FindMaxCrossSubarray    (int *A,int low,int mid,int high){    int left_max =mid;    long long leftMaxSum = LLONG_MIN;    long long sum=0;    for(int i = mid;i>=low;--i)    {        sum=sum+A[i];        if(sum>leftMaxSum)        {            left_max = i;            leftMaxSum = sum;        }    }    int right_max = mid+1;    long long rightMaxSum=LLONG_MIN;    sum = 0;    for(int j=mid+1;j<=high;++j)    {        sum=sum+A[j];        if(sum>rightMaxSum)        {            right_max = j;            rightMaxSum = sum;        }    }    return {left_max,right_max,leftMaxSum+rightMaxSum};}resultType FindMaxSubArray(int *A,int low,int high){    if(low == high)    {        return {low,high,A[low]};    }    else    {        int mid = (low+high)/2;        resultType leftResult = FindMaxSubArray(A,low,mid);        resultType rightResult = FindMaxSubArray(A,mid+1,high);        resultType crossResult = FindMaxCrossSubarray(A,low,mid,high);        if(get<2>(leftResult)>get<2>(rightResult)&&get<2>(leftResult)>get<2>(crossResult))        {            return leftResult;        }        else if(get<2>(rightResult)>get<2>(leftResult)&&get<2>(rightResult)>get<2>(crossResult))        {            return rightResult;        }        else        {            return crossResult;        }      } }int main(){    int test[9]{-2,1,-3,4,-1,2,1,-5,4};    resultType result = FindMaxSubArray(test,0,sizeof(test)/sizeof(int)-1);    for(int i=get<0>(result);i<=get<1>(result);i++)    {        cout<<test[i]<<ends;    }    cout<<endl<<get<2>(result);    system("pause");    return 0;}

分治法优化

• 思路为改变计算跨越mid的最大子数组的方法。[l...r]这个区间的最大子数组可能为[l...m]的最大子数组和[m+1...r]的最大子数组，或包含m和m+1的最大子数组（即跨越mid）。统计四个量，分别为：

  1. lsum:以l开头的最大子数组
  2. rsum：以r结尾的最大子数组
  3. isum：当前所有元素的和
  4. msum：当前最大子数组
     

• 则在合并时根据左、右两侧的统计量更新合并后的统计量，最终得到的msum即为最大子数组。更新规则为

  1. 合并后的lsum为左侧的子串的lsum或左侧子串的isum加上右侧子串的lsum，取较大值为合并后的lsum
  2. 合并后的rsum为右侧子串的rsum或者右侧子串的isum加上左侧子串的rsum，取较大值为合并后的rsum
  3. 合并后的isum为左右两侧isum之和
  4. 合并后的msum为左侧的msum或右侧的msum或左侧的rsum加上右侧lsum三者取最大值为新的msum

• 伪码实现：

  FIND-MAX-SUBARRAY(A,low,high)    if low==high        return (A[low],A[low],A[low],A[low])//四个数分别问lsum，rsum，isum，msum    else        mid = (low+high)/2        (l_lsum,l_rsum,l_isum,l_msum)=FIND-MAX-SUBARRAY(A,low,mid)        (r_lsum,r_rsum,r_isum,r_msum)=FIND-MAX-SUBARRAY(A,mid+1,high)        lsum=l_lsum>(l_isum+r_lsum) ? l_lsum :l_isum+r_lsum        rsum=r_rsum>(r_isum+l_rsum) ? r_rsum:r_isum+l_rsum        isum=l_isum+r_isum        if l_msum>r_msum and l_msum>(l_rsum+r_lsum)            return (lsum,rsum,isum,l_msum)        if r_msum>l_msum and r_msum>(l_rsum+r_lsum)            return (lsum,rsum,isum,r_msum)        else            return (lsum,rsum,isum,l_rsum+r_lsum)

• 时间复杂度分析：分解部分时间复杂度为常数，合并部分时间复杂度也为常数。则T(n)=2T(n/2)+(1),即T(n)=(lgn)

• 源码实现：以下源码只求出的最大子数组的和，没有保存最大子数组对应的下标

  #include <iostream>#include <tuple>using namespace std;using resultType = tuple<long long,long long,long long,long long>;resultType FindMaxSubArray(int *A,int low,int high){    if(low==high)    {        return {A[low],A[low],A[low],A[low]};    }    else    {        int mid = (low+high)/2;        resultType lResult =FindMaxSubArray(A,low,mid);        resultType rResult =FindMaxSubArray(A,mid+1,high);        int l_lsum = get<0>(lResult),        l_rsum = get<1>(lResult),        l_isum = get<2>(lResult),        l_msum = get<3>(lResult);        int r_lsum = get<0>(rResult),        r_rsum = get<1>(rResult),        r_isum = get<2>(rResult),        r_msum = get<3>(rResult);        int lsum = l_lsum > (l_isum+r_lsum) ? l_lsum :l_isum+r_lsum;        int rsum = r_rsum > (r_isum+l_rsum) ? r_rsum:r_isum+l_rsum;        int isum = l_isum+r_isum;        if(l_msum>r_msum && l_msum>(l_rsum+r_lsum))        {            return {lsum,rsum,isum,l_msum};        }              else if(r_msum>l_msum && r_msum>(l_rsum+r_lsum))        {            return {lsum,rsum,isum,r_msum};        }        else        {            return {lsum,rsum,isum,l_rsum+r_lsum};        }            }}int GetMaxSubArrayValue(int *A,int low,int high){    resultType result = FindMaxSubArray(A,low,high);    return get<3>(result);}int main(){    int test[9]{-2,1,-3,4,-1,2,1,-5,4};    int result = GetMaxSubArrayValue(test,0,sizeof(test)/sizeof(int)-1);    cout<<endl<<result;    system("pause");    return 0;}

最大子数组问题贪心法求解

• 思路如果已知数组A[1...j]的最大组数组，则A[1...j+1]的最大子数组为A[1...j]的子数组，或者是以j+1为末尾元素的子数组。以j+1为结尾的子数组有两种，一种是只包含j+1位置上的元素，另外一种为j+1前的子序列加上j+1。如果j+1前的子序列和为正数，则包含之前的子序列的数组元素和大于只包含j+1位置元素的数组。按照这种思路从左到右遍历数组即可得到最大子数组

• 伪码：

  FIND-MAX-SUBARRAY(A,low,high)    cursum=MIN//用于保存当前求和的结果    curleft=0//用于保存当前的计算的可能的最大子数组的左边界    maxsum=MIN//用于保存已遍历部分的最大和    maxleft=0//保存已遍历部分的最大和对应的左边界    maxright=0//保存已遍历部分的最大和对应的右边界    for i=low to high        if cursum<0            cursum=A[i]            curleft=i        else            cursum=cursum+A[i]        if cursum>maxsum            maxsum=cursum            maxleft=curleft            maxright=i    return (maxsum,maxleft,maxright)

• 时间复杂度分析：只遍历一遍，时间复杂度为(n)

• 源码实现：

  #include <iostream>#include <tuple>#include <limits.h>using namespace std;using ResultType=tuple<long long,int,int>;ResultType FindMaxSubArray(int *A,int low,int high){    long long cursum =  LLONG_MIN;    int curleft = 0;    long long maxsum = LLONG_MIN;    int maxleft = 0;    int maxright = 0;    for(int n=low;n<=high;++n)    {        if(cursum<0)        {            cursum=A[n];            curleft=n;        }        else        {            cursum+=A[n];        }        if(cursum>maxsum)        {            maxsum = cursum;            maxleft = curleft;            maxright = n;        }    }    return {maxsum,maxleft,maxright};}int main(){    int test[9]{-2,1,-3,4,-1,2,1,-5,4};    ResultType result = FindMaxSubArray(test,0,sizeof(test)/sizeof(int)-1);    for(int i=get<1>(result);i<=get<2>(result);i++)    {        cout<<test[i]<<ends;    }    cout<<endl<<get<0>(result);    system("pause");    return 0;}