アルゴリズム(一)管窥アルゴリズム
1626 ワード
1.1最大連続サブ配列
配列A[0,1,...,n−1]を与え、その配列の和が最大になるように、Aの連続するサブ配列を求める.
例:配列:1,-2,3,10,-4,7,2,-5
最大サブ配列:3,10,-4,7,2
1.1.1暴力法
直接解く.時間複雑度o(n^3).(C+++を覚えたら!)
1.1.2分法
配列を中間から分離すると、最も大きなサブ配列は完全に左半分の配列にあるか、完全に右半分の配列にあるか、境界点にまたがっているかのいずれかです.完全に左右の配列で、再帰的に解決します.境界点にまたがる:実際には左配列の最大接尾辞と右配列の最大接頭辞の和です.したがって,分布点から前へ掃き,後ろへ掃くとよい.コード:
配列A[0,1,...,n−1]を与え、その配列の和が最大になるように、Aの連続するサブ配列を求める.
例:配列:1,-2,3,10,-4,7,2,-5
最大サブ配列:3,10,-4,7,2
1.1.1暴力法
直接解く.時間複雑度o(n^3).(C+++を覚えたら!)
#include
#include
int MaxSubArray(int a[],int n)
{
int max=a[0];
int crr;
for(int i=0;imax)
max=crr;
}
}
return max;
}
int main()
{
printf(" :
");
int n;
scanf("%d",&n);
int a[n];
printf(" :
");
for(int i=0;i
1.1.2分法
配列を中間から分離すると、最も大きなサブ配列は完全に左半分の配列にあるか、完全に右半分の配列にあるか、境界点にまたがっているかのいずれかです.完全に左右の配列で、再帰的に解決します.境界点にまたがる:実際には左配列の最大接尾辞と右配列の最大接頭辞の和です.したがって,分布点から前へ掃き,後ろへ掃くとよい.コード:
#include
#include
#define max(a,b) (a>b)?a:b
int max2(int a,int b,int c)
{
int big;
if(a >= b)
big = a;
else
big = b;
if(c> big)
big = c;
return big;
}
int MaxSub(int a[],int from,int to)
{
if(to==from)
return a[from];
int mid=(from+to)/2;
int m1=MaxSub(a,from,mid);
int m2=MaxSub(a,mid-1,to);
int i,left=a[mid],now=a[mid];
for(i=mid-1;i>=from;i--)
{
now+=a[i];
left=max(now,left);
}
int right=a[mid+1];
now=a[mid+1];
for(i=mid+2;i<=to;i++)
{
now+=a[i];
right=max(now,right);
}
int m3=left+right;
return max2(m1,m2,m3);
}
int main()
{
printf(" :
");
int n;
scanf("%d",&n);
int a[n];
printf(" :
");
for(int i=0;i