最大サブ配列の擬似コードとコード実装

12220 ワード

ぎじふごう
findMaxCrossingSubarray(A,low,mid,high)
    sum=0
    leftSum=-9999//      
    for i=mid downto low
        sum=sum+A[i]
        if sum>leftSum
            leftSum=sum
            maxLeft=i
    sum=0
    rightSum=-9999
    for j=mid+1 to high
        sum=sum+A[j]
        if sum>rightSum
            rightSum=sum
            maxRight=j
    return [maxLeft,maxRight,leftSum+rightSum]
    findMaximumSubArray(A,low,high)
        if low==high
            return [low,high,A[low]]
        else
            mid=floor((low+high)/2)
            [leftLow,leftHigh,leftSum]=
                findMaximumSubArray(A,low,mid)
            [rightLow,rightHigh,rightSum]=
                findMaximumSubArray(A,mid+1,high)
            [midLow,midHigh,midSum]=
                findMaxCrossingSubarray(A,low,mid,high)
            if(leftSum>=midSum and leftSum>=rightSum)
                return [leftLow,leftHigh,leftSum]
            else if(rightSum>=leftSum and rightSum>=midSum)
                return [rightLow,rightHigh,rightSum]
            else
                return [midLow,midHigh,midSum]

c言語実装
struct desc{
    int a[3];
}x,y,leftX,midX,rightX;

struct desc findMaxCrossingSubarray(int A[],int low,int mid,int hight){
    int leftSum=-9999;//       
    int sum=0;
    int i,j;
    int maxLeft;
    for(i=mid;i>=low;i--){
        sum=sum+A[i];
        if (sum>leftSum){
            leftSum=sum;
            maxLeft=i;
        }
    }
    int rightSum=-9999;
    sum=0;
    int maxRight;
    for(j=mid+1;j<=hight;j++){
        sum=sum+A[j];
        if(sum>rightSum){
            rightSum=sum;
            maxRight=j;
        }
    }
    x.a[0]=maxLeft;
    x.a[1]=maxRight;
    x.a[2]=leftSum+rightSum;
    return x;
    //printf("         :%d,         :%d,         :%d",maxLeft,maxRight,leftSum+rightSum);
}
struct desc findMaximumSubArray(int A[],int low,int hight){
    int mid;
    if(hight==low){
        y.a[0]=low;
        y.a[1]=hight;
        y.a[2]=A[low];
        return y;
    }
    else{
        mid=floor((low+hight)/2);
        leftX=findMaximumSubArray(A,low,mid);
        rightX=findMaximumSubArray(A,mid+1,hight);
        midX=findMaxCrossingSubarray(A,low,mid,hight);
        if(leftX.a[2]>=rightX.a[2] && leftX.a[2]>=midX.a[2])
            return leftX;
        else if(rightX.a[2]>=leftX.a[2] && rightX.a[2]>=midX.a[2])
            return rightX;
        else
            return midX;
    }
}
void main(){
    int A[]={1,-2,3,4,-5};
    struct desc final=findMaximumSubArray(A,0,4);
    printf("         :%d,         :%d,         :%d",final.a[0],final.a[1],final.a[2]);
}

JAva実装
public class Main {

    public static void main(String[] args) {
        int [] arr={1,-2,3,4,5};
        List finalDesc=findMaximumSubArray(arr,0,4);
        System.out.println("         :"+finalDesc.get(0)+"
:"
+finalDesc.get(1)+"
:"
+finalDesc.get(2)); } public static List findMaxCrossingSubArray(int [] arr,int low,int mid,int hight){ int sum=0; int leftSum=-9999; int maxLeft=0; for(int i=mid;i>=0;i--){ sum=sum+arr[i]; if(sum>leftSum){ leftSum=sum; maxLeft=i; } } sum=0; int rightSum=-9999; int maxRight=0; for(int j=mid+1;j<=hight;j++){ sum=sum+arr[j]; if(sum>rightSum){ rightSum=sum; maxRight=j; } } List descList=new ArrayList(); descList.add(maxLeft); descList.add(maxRight); descList.add(leftSum+rightSum); return descList; } public static List findMaximumSubArray(int [] arr,int low,int hight){ List descList=new ArrayList(); int mid=0; if(low==hight){ descList.add(low); descList.add(hight); descList.add(arr[low]); return descList; } else { mid=(int)Math.floor((low+hight)/2); List leftDesc=findMaximumSubArray(arr,low,mid); List rightDesc=findMaximumSubArray(arr,mid+1,hight); List midDesc=findMaxCrossingSubArray(arr,low,mid,hight); if(leftDesc.get(2)>=rightDesc.get(2) && leftDesc.get(2)>=midDesc.get(2)) return leftDesc; else if(rightDesc.get(2)>=leftDesc.get(2) && rightDesc.get(2)>=midDesc.get(2)) return rightDesc; else return midDesc; } } }