アルゴリズム(一)管窥アルゴリズム

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+++を覚えたら!)

#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