最大部分列とアルゴリズム分析
問題の説明: n 個の整数列 {a1, a2,...,an} が与えられた場合、関数 f(i,j)=max{0,Σa k}(k: i から j まで連続して取得);
問題は、連続するサブ列の合計の最大値を見つけることです。最大値が負の数の場合は、0 を取得します。 8 つの数列 {-1,2,-3,4,-2,5,-8,3} として、Namo の最大部分列合計は 4 (-2) 5=7 です。
この問題には複雑度の異なる 4 つのアルゴリズムがあり、アルゴリズム 1 ~ 4 の時間計算量は O(n3)、O(n2)、O(nlogn) です。 、O(n);
アルゴリズム 1:
最も直接的な方法は、すべての状況をリストする網羅的な方法であり、次の式の左端 i を設定できます。 //最大のサブ列と網羅的なメソッド#include
名前空間 std を使用;
int Find_Maxsun(int*a, int n);
int main(){
int n, i;
int a[100];
cin >> n ;
cout << "数値:" <
を入力してください。 n; i )
cin >> a[i];
cout return 0;
}
Find_Maxsun(int*a , int n){
int MaxSun = 0, i, j, k;
int NowSum;
for (i = 0; i
for (k = i; k NowSum = a[k]; /* a[i] から a[j] までのシーケンス */
if (NowSum>MaxSun)
MaxSun = NowSum;
}
return MaxSun;
}
3) です。もちろん、最も愚かなアルゴリズムですが、データが非常に難しい場合、たとえそれが死ぬほど計算されたとしても、
j が追加されるたびに、for ループの 3 番目のレベルが明らかにわかります。 -列の合計を再度計算する必要があるので、j-1 の結果を使用しないのはなぜでしょうか。つまり、j-1 の結果を保存します。ステップ j の結果を計算するときは、ステップ j-1 に基づいて a[j] を加算するだけで済みます。したがって、アルゴリズム 2 が存在します。アルゴリズム 2:
#includeusing namespace std;
int Find_Maxsun2(int*a, int n);
int main(){
int n, i;
int a[100];
cin >> n;
cout <
cout << ; Find_Maxsun2(a, n) <
}
int Find_Maxsun2(int*a, int n){
int i, j, NewSum = 0, MaxSum = 0;
for (i = 0; i
for (j = i; j NewSum = a[j] /* j-1 条件で毎回 NewSum を更新します*/
if (NewSum>MaxSum) / *MaxSum を更新* /
MaxSum = NewSum;
}
}
return MaxSum;
}
2)、これは明らかに私たちが望む複雑さではありません。
アルゴリズム 3:
アルゴリズム 3 は分割統治の考え方を使用します。基本的な考え方は自明です。最初に分割してから征服し、分解します。問題を小さな問題に分割し、合計できる小さな問題を解決するには、元のシーケンスを 2 つに分割し、最大のサブシーケンスを左側、右側、または境界を越えて配置します。 基本的な考え方は次のとおりです。 🎜>ステップ 1: 元のシーケンスを 2 つに分割し、左のシーケンスと右のシーケンスに分割します。
ステップ 2: サブシーケンス S left と S right を再帰的に見つけます。
パート 3: 中心線から両側に向かってスキャンして、中心線と S を横切る最大のサブシーケンスを見つけます。
ステップ 4: S=max{S left, S middle, S right} を見つける
コードは次のように実装されます。
#include
名前空間 std を使用;
int Find_MaxSum3(int*a,int low,int high);
int Max(int a,int b,int c);
int main(){
int n, i;
int a[100];
cin >> n;
cout << "を入力してください。 < n << " 数値:" <
< < Find_MaxSum3(a,0,n-1) <
}
int Find_MaxSum3(int*a,int low,int high) int MaxSum = 0, MidSum, LeftSum, RightSum,i;
MidSum = 0;
if (low == high){ /*再帰の終了条件*/
if (a[low] > 0)
return a[low];
else
return 0;
}
int mid = (low high) / 2 //スコアの中間点を見つける
LeftSum = Find_MaxSum3( a, low, mid); /*左のシーケンスの最大合計を再帰的に求めます*/
RightSum = Find_MaxSum3(a, mid 1, high); /*右のシーケンスの最大のサブシーケンスの合計を再帰的に求めます*/
/*そうすれば、中間の国境を越えたシーケンスの最大合計を見つけることができます */
int NewLeft = 0,Max_BorderLeft=0, NewRight = 0,Max_BorderRight=0;
for (i = Mid; i >= low; i--) { /*左をスキャンして最大合計を見つけます*/
NewLeft = a[i];
if (NewLeft > Max_BorderLeft)
Max_BorderLeft = NewLeft ;
}
for (i = mid 1; i NewRight =a[i];
if (NewRight >= Max_BorderRight)
Max_BorderRight = NewRight ;
}
MidSum = Max_BorderRight Max_BorderLeft;
return Max(LeftSum, MidSum, RightSum) /*処理の結果を返します*/
}
int Max(int a, int b, int c){ /*3 つの中で最大の数値を見つける*/
if ( a>= b&&a >= c)
return a ;
if (b >= a&&b >= c )
return b;
if (c >= b&&c>=a)
return c;
}
kT( n/2k) kO(n)=2kT(1) kO(n) (n=2 の場合) k)=n nlogn=O (nlogn);
このアルゴリズムは非常に優れていますが、最速のアルゴリズムではありません。アルゴリズム 4:
アルゴリズム 4 はオンライン処理と呼ばれます。これは、データが読み込まれるたびに、時間内に処理され、得られた結果が現在読み込まれているデータに当てはまります。つまり、アルゴリズムはどの位置でも正しい解を与えることができ、アルゴリズムは次のことを行うことができます。読みながら正しい解決策を見つけてください。 #include名前空間 std を使用;
int Find_MaxSum4(int*a, int n);
int main(){
int n, i;
int a[100];
cin >>
cout <
cout return 0;
}
int Find_MaxSum4(int*a, int n){
int i, NewSum = 0, MaxSum = 0;
for (i = 0; i NewSum = a[i]; /*現在のサブシーケンス合計*/
if (MaxSum
if ( NewSum < 0) /*0 未満の場合は破棄します*/
NewSum = 0;
}
return MaxSum;
}