連続サブ配列の最大和の3種類の古典的なアルゴリズム

タイトルの説明
1つの配列にはN個の要素があり、連続サブ配列の最大和を求める.例えば,[−1,2,1],および最大の連続サブ配列は[2,1],およびその和は3である.
入出力サンプル
入力(最初の数はシーケンス数)3-12 1 1
出力3
次に、時間の複雑さに基づいて、次のアルゴリズムを徐々に最適化します.
一.暴力の解き方
まず、最初の要素をはじめとする最も大きなサブ配列を見つけ、次に、2番目の要素をはじめとする最も大きなサブ配列を見つけます.

/*
    ,     O（n*n）
             ，
            ，     ，
             ，    。
*/
int MaxSubSum1(int *arr,int len)
{
	int i,j;
	int MaxSum = 0;
	//              
	for(i=0;i<len;i++)
	{
		int CurSum = 0;
		//       
		for(j=i;j<len;j++)
		{
			CurSum += arr[j];
			if(CurSum > MaxSum)
				MaxSum = CurSum;
		}
	}
	return MaxSum;
}

時間複雑度o(n*n)
分治解
配列を中間から2つのサブ配列に分けることを考慮すると,最大の比は3つのケースの1つに現れる.

1.完全左配列

2.完全に右側の配列

に位置する

3.中点を跨ぐ、左右の配列が中点に近い部分

を含む
具体的には、左右のサブ配列を再帰的に2つの配列に分け、サブ配列に1つの要素しかないまで

int Max3(int a,int b,int c)
{
     int Max = a;
     if(b>MAX)
	     Max = b;
	  if(c > Max)
	     Max = c;
	   return Max;
}
int MaxSubSum2(int *arr,int left ,int right)
{
	int MaxleftSum,MaxRightSum;
	int MaxLfetBorderSum,MaxRightBorderSum;//             
	int LeftBorderSum,RightBorderSum;//             
	int i,center;
    
    //          
    if(left == right)
        if(arr[left]>0)
            return arr[left];
        else 
           return 0;

	//               
	center  = (left + right)/2;
	MaxLeftBorderSum = 0;
	LeftBorderSum = 0;
	for(i = center;i>=left;i--)
	{
	     LeftBorderSum += arr[i];
	     if(LeftBorderSum >MaxLeftBorderSum)
			     MaxLeftBorderSum = LeftBorderSum;
	}
	 MaxRightBorderSum = 0;
	RightBorderSum = 0;
	for(i=center+1;i<=right;i++)
	{
		RightBorderSum += arr[i];
		if(RightBorderSum > MaxRightBorderSum)
			MaxRightBorderSum = RightBorderSum;
	}

    //          
    MaxLeftSum = MaxSubSum2(arr,left,center);
	MaxRightSum = MaxSubSum2(arr,center+1,right);
    
    //         
	return Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum);
}
//       
int MaxSubSum2_1(int *arr,int len)
{
	return MaxSubSum2(arr,0,len-1);
}         

このアルゴリズムの時間的複雑度をT(n)とすると,T(n)=2 T(n/2)+O(n),T(1)=1となる.時間的複雑度T(n)＝O(nlogn)を逐次繰返しした.
せんけいじかんアルゴリズム
このアルゴリズムは、要素が0未満になるたびに、次の要素から加算を再開します.

/*
    ，     O（n）
                  
        ，             0
*/
int MaxSubSum3(int *arr,int len)
{
	int i;
	int MaxSum = 0;
	int CurSum = 0;
	for(i=0;i<len;i++)
	{
		CurSum += arr[i];
		if(CurSum > MaxSum)
			MaxSum = CurSum;
		//         0   ，
		//                    ，
		//       0，           
		if(CurSum < 0)
			CurSum = 0;
	}
	return MaxSum;
}

アルゴリズムの複雑さ:O(n)で、このアルゴリズムの1つに付属しているのは、データを1回だけスキャンし、要素が読み込まれて処理されると、記憶される必要がなくなります.したがって、配列がディスクまたはテープ上にある場合、配列の任意の部分をプライマリ・ストレージに格納する必要はありません.それだけでなく、任意の時点で、このアルゴリズムは、読み込まれたデータに対して最大のサブ配列を与えることができる(他の2つのアルゴリズムはこのような特性を持たない).このような特性を持つアルゴリズムをオンラインアルゴリズムと呼ぶ.
変換元:[http://blog.csdn.net/ns_code/article/details/20942045]