乐趣区

leetcode最大子序和leetcode53

jiezi

最大子序和

给定一个整数数组 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+1
FIND-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;
}
退出移动版