最大子序列和问题

包括两个方法，分治法与最优起点法。生成随机数写入文件，从文件读取数据，求出最大子序列和并且把子序列输出到文件中

还有两个算法运行的时间。

#include <iostream>
#include <fstream>
#include <vector>
#include <time.h>
#define length 5
using namespace std;
int max3(int a,int b,int c){
    if(a>b)
        return a>c?a:c;
    else
        return b>c?b:c;
}

int maxSubArray(int a[],int l,int r){
    if(r==l)
        return a[l];

    int mid=(r+l)/2;
    int maxLeftSum=maxSubArray(a,l,mid);
    int maxRightSum=maxSubArray(a,mid+1,r);

    int maxLeftBorderSum=0,leftBorderSum=0;
    for(int i=mid;i>=l;i--){
        leftBorderSum+=a[i];
        if(maxLeftBorderSum<leftBorderSum)
            maxLeftBorderSum=leftBorderSum;
    }

    int maxRightBorderSum=0,rightBorderSum=0;
    for(int i=mid+1;i<=r;i++){
        rightBorderSum+=a[i];
        if(rightBorderSum>maxRightBorderSum)
            maxRightBorderSum=rightBorderSum;
    }

    return max3(maxRightSum,maxLeftSum,maxRightBorderSum+maxLeftBorderSum);

}

int e=0,b=0;
int a[length];
std::vector<int> s{0};
int maxSubArray2(int a[],int size){
    int sum=0,maxSum=0;
    for(int i=0;i<size;i++){
        sum+=a[i];
       // cout<<a[i]<<" "<< sum<<endl;

        if(maxSum<sum) {
            maxSum = sum;
            e=i;
        }
        else if(sum<0){
            s.push_back(i+1);
            sum=0;
        }
    }
    return maxSum;
}


int main() {
    //std::cout << "Hello, World!" << std::endl;
    srand((unsigned)time(NULL));
    clock_t start1,start2,end1,end2;
    int maxSum=0;
    ofstream otf;
    otf.open("input.txt");
    for(int i=0;i<length;i++)
        otf << random() % 10 - 4 << " ";
    otf.close();

    ifstream itf("/Users/meser/Documents/AlgorithmTest/test1/cmake-build-debug/input.txt");
    for(int i=0;i<length;i++) {
        itf >> a[i];
        //cout<<a[i]<<" ";
    }
    itf.close();
    start1=clock();
    int result=maxSubArray(a,0,length-1);
    end1=clock();
    cout<<result<<"  运行时间为 "<<end1-start1<<endl;
    start2=clock();
    int result1=maxSubArray2(a,length);
    end2=clock();
    cout<<result1<<"  运行时间为 "<<end2-start2<<endl;

    for(int i=0;i<s.size();i++)
        if(s[i]<=e)
            b=s[i];
    //for(int i=b;i<=e;i++)
    //    maxSum+=a[i];
    // cout<<maxSum<<endl;
    otf.open("output.txt");
    for(int i=b;i<=e;i++){
        otf<<a[i]<<" ";
    }
    otf.close();

    return 0;
}