Максимальная сумма Subarray и те, индекс-разделяй и властвуй - PullRequest
Новая
       29

Максимальная сумма Subarray и те, индекс-разделяй и властвуй

0 голосов
/ 22 сентября 2019

Мой код выше, чтобы найти максимальную сумму подмассива и найти начальный индекс, конечный индекс этого подмассива. 

int Max(int a,int b){return (a>b)?a:b;}
int Max(int a,int b,int c){return Max(Max(a,b),c);}
int MaxAcrossSubArray(int arr[],int l,int m,int r,int &Start,int &End) 
{
    Start=m;//initialize start index
    int sum=arr[m];
    int sum_l=arr[m];
    for(int i=m-1;i>=l;--i)//include mid(---------|)
    {
        sum+=arr[i];
        if(sum>sum_l)
        {
            Start=i;
            sum_l=sum;
        }

    }
    End=m+1;//initialize end index
    sum=arr[m+1];
    int sum_r=arr[m+1];
    for(int i=m+2;i<=r;++i)//include mid(|-----------------)
    {
        sum+=arr[i];
        if(sum>sum_r){
            End=i;
            sum_r=sum;
        }
    }
    return sum_l+sum_r;//(-----------|---------------------)

}
int MaxSubArray(int arr[],int l,int r,int &Start,int &End)
{
    if(l==r)
    {
        Start=l;
        End=r;
        return arr[l];
    }

    else
    {
        int mid=(l+r)/2;
        int a=MaxSubArray(arr,l,mid,Start,End);
        int b=MaxSubArray(arr,mid+1,r,Start,End);
        int c=MaxAcrossSubArray(arr,l,mid,r,Start,End);
        int Maximum=Max(a,b,c);

        if(Maximum==a)
            return MaxSubArray(arr,l,mid,Start,End);
        else if(Maximum==b)
            return MaxSubArray(arr,mid+1,r,Start,End);
        else
            return MaxAcrossSubArray(arr,l,mid,r,Start,End);
    }

}

Мой алгоритм работает хорошо в любом случае, но я все еще нуждаюсь в вас, ребята, помогите мне улучшить мой алгоритмк лучшему. Есть ли способ сделать это лучше?

...