算法导论作业（1）最大子数组问题

#include <limits.h>
#include <vector>
#include <tuple>
using namespace std;
tuple<int,int,int> find_max_cross_subarray(vector<int> A,int low,int mid,int high){
    int left_sum=INT_MIN;
    int sum=0;
    int max_left=0;
    int max_right=0;
    
    for(int i=mid;i>=low;i--){
        sum=sum+A[i];
        if(sum>left_sum){
            left_sum=sum;
            max_left=i;
        }
    }
    sum=0;
    // 靠近中线以右最大
    int right_sum=INT_MIN;
    // 注意这里的j应该是j<=high,如果写成j<high是错误的,原因在于下一次递归时,我们无法访问A[mid]。
    for(int j=mid+1;j<=high;j++){
        sum=sum+A[j];
        if(sum>right_sum){
            right_sum=sum;
            max_right=j;
        }
    }
    return make_tuple(max_left,max_right,left_sum+right_sum);
}
tuple<int,int,int> find_max_subarray(vector<int> A,int low,int high){
    if(high==low)
        return make_tuple(low,high,A[low]);
    else{
        int mid=(low+high)/2;
        // 左边
        int left_low,left_high,left_sum;
        tie(left_low,left_high,left_sum)=find_max_subarray(A,low,mid);
        // 右边
        int right_low,right_high,right_sum;
        tie(right_low,right_high,right_sum)=find_max_subarray(A,mid+1,high);
        // 中间
        int cross_low,cross_high,cross_sum;
        tie(cross_low,cross_high,cross_sum)=find_max_cross_subarray(A,low,mid,high);
        if(left_sum>=right_sum && left_sum>=cross_sum)
            return make_tuple(left_low,left_high,left_sum);
        else if(right_sum>=left_sum && right_sum>=cross_sum)
            return make_tuple(right_low,right_high,right_sum);
        else return make_tuple(cross_low,cross_high,cross_sum);
    }
}
int () {
    vector<int>A{10,-2,-1,1,1,2,2,3,-4,-5};
    int low,high,sum;
    tie(low,high,sum)=find_max_subarray(A,0,9);
    cout<<"此处以c++数组格式记录位置,即第一个元素在位置0。"<<endl;
    cout<<endl;
    cout << "左边界位置: "<<low<<endl;
    cout<<"右边界位置: "<<high<<endl;
    cout<<"最大子数组和为: "<<sum << endl;
    return 0;
}