最大サブ配列の擬似コードとコード実装
12220 ワード
ぎじふごう
c言語実装
JAva実装
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;
}
}
}