配列の中で最も長い増分のサブシーケンスの解決方法を求めます
4836 ワード
ストレージ拡張アルゴリズムn 2プログラミングcは、時間的複雑度ができるだけ低いプログラムを書き、1次元配列(N要素)の中で最も長い増分サブシーケンスの長さを求める.
例えば、配列1,−1,2,−3,4,−5,6,−7において、その最長の増分子配列は、1,2,4,6または−1,2,4,6である.(プログラミングの美P 198-202)
分析と解法はテーマの要求に基づいて、1次元配列の中の最長の増分子シーケンスを求めて、つまり1つの符号のシーケンスb[0]、b[1],...,b[m](0<=b[0]解法1後効性のない定義によれば,各段階を一定の順序で並べた後,ある与えられた段階状態にとって,以前の各段階の状態は将来の決定に直接影響することができず,間接的に現在のこの状態によって影響するしかないことが分かった.言い換えれば、各状態は歴史の完全な総括である.
同様に,シーケンス1,−1,2,−3,4,−5,6,−7を例にとると,6の発見に直接影響を及ぼさないため,4の発見後,4の以前の2つの値が具体的にどうであるかには関心がない.したがって,この問題は無後効性を満たし,動的計画を用いることで解決できる.
ターゲット列:1,−1,2,−3,4,−5,6,−7を数値の法則により解析できた.
iを使用して現在の遍歴の位置を表す
i=1の場合、最長のインクリメントシーケンスは(1)、シーケンス長は1であることは明らかである.
i=2がそうである場合、−1<1のためである.したがって、最初の値を破棄してシリアルを再確立する必要があります.現在の増分シーケンスは(-1)、長さは1です.
i=3の場合、2>1,2>−1である.したがって,最長の増分シーケンスは(1,2),(−1,2),長さは2であった.ここで,2の前が1であるか−1であるかは,後のインクリメントシーケンスを求めることに直接影響しない.(ただし、他の場合は影響する可能性があります)
このように推すと,我々は次のような結論を導いた.
ターゲット配列array[]の最初のi要素のうち、最長増分子シーケンスの長さはLIS[i]であると仮定する.では、
LIS[i+1]=max{1,LIS[k]+1}, array[i+1]>array[k], for any k <= i
すなわちarray[i+1]がarray[k]より大きい場合、i+1番目の要素はLIS[k]の長いサブシーケンスの後に接続されてより長いサブシーケンスを構成することができる.これと同時にarray[i+1]自体が少なくとも1つの長さのサブシーケンスを構成することができる.
上記の分析に基づいて、コードリストを得ることができます.
C++コード:
この方法の時間的複雑さはO(N 2＋N)＝O(N 2)である.
解法2前の解析では,i+1番目の元素を考察する際に,前のi個の元素の分布を考慮しない.次に,i+1番目の元素を考察する際に,前のi個の元素の場合を考慮する別の観点から解析する.
前のi個の要素のいずれかの増分サブシーケンスについて、このサブシーケンスの最大要素がarray[i+1]よりも小さい場合、array[i+1]をこのサブシーケンスの後に加算して、新しい増分サブシーケンスを構成することができる.
例えばi=4の場合、ターゲットシーケンスは1,−1,2,−3,4,−5,6,−7の最長インクリメントシーケンスは(1,2),(−1,2)である.
では,4>2であれば,4を直接前のサブシーケンスに増やして新しい増分サブシーケンスを形成することができる.
従って、array[i+1]よりも最大の要素が小さく、長さができるだけ長くなるように、前のi要素の1つの増分サブシーケンスを見つけたい.このようにarray[i+1]をインクリメンタルサブシーケンスに加算すると、array[i+1]を最大要素とする最長インクリメンタルサブシーケンスが見つかる.
配列の前のi個の要素のうちarray[i]を最大要素とする最長増分子シーケンスの長さはLIS[i]であると仮定する.
同時に、仮定:
長さ1の増分サブシーケンスの最大要素の最小値はMaxV[1]である.
長さ2の増分サブシーケンスの最大要素の最小値はMaxV[2]である.
……
長さLIS[i]の増分サブシーケンスの最大要素の最小値はMaxV[LIS[i]]である.
本サイクル不変式Pは、P:kがシーケンスa[0:i]の最長増分子シーケンスの長さであり、0≦ii−1からiまでのサイクルではa[i]の値が重要な役割を果たすことが容易に分かる.a[i]がシーケンスa[0;i−1]の最長増分子シーケンスの長さを拡張できる場合、k=k+1であり、そうでなければkは変わらない.a[0;i−1]における長さkの最長増分子シーケンスの終端要素がa[j](0≦j≦i−1)であるとすると、a[i]≧a[j]のときに拡張でき、そうでなければ拡張できない.シーケンスa[0;i-1]にkの長さの最長増分サブシーケンスが複数ある場合、どのような情報を格納する必要がありますか?シーケンスa[0;i−1]のすべての長さkの増分サブシーケンスにおける末尾要素の最小値b[k]が格納されている限り、容易に分かる.したがって、循環不変式Pを以下のように増強する必要がある.
P:0≤i＜n;kは、シーケンスa[0;i]の最長増分子シーケンスの長さである.
b[k]は、シーケンスa[0;i]のすべての長さkの増分サブシーケンスの最小終端要素値である.
従って、帰納仮定は、計算シーケンスa[0;i−1](i帰納仮定を強化すると、i−1からiへのサイクルでは、a[i]≧b[k]の場合、k=k+1、b[k]=a[i]となり、そうでなければk値は変わらない.a[i]≧b[k]の場合、k値は増加し、b[k]の値はa[i]であることに留意されたい.では、a[i]
例えば、配列1,−1,2,−3,4,−5,6,−7において、その最長の増分子配列は、1,2,4,6または−1,2,4,6である.(プログラミングの美P 198-202)
分析と解法はテーマの要求に基づいて、1次元配列の中の最長の増分子シーケンスを求めて、つまり1つの符号のシーケンスb[0]、b[1],...,b[m](0<=b[0]
同様に,シーケンス1,−1,2,−3,4,−5,6,−7を例にとると,6の発見に直接影響を及ぼさないため,4の発見後,4の以前の2つの値が具体的にどうであるかには関心がない.したがって,この問題は無後効性を満たし,動的計画を用いることで解決できる.
ターゲット列:1,−1,2,−3,4,−5,6,−7を数値の法則により解析できた.
iを使用して現在の遍歴の位置を表す
i=1の場合、最長のインクリメントシーケンスは(1)、シーケンス長は1であることは明らかである.
i=2がそうである場合、−1<1のためである.したがって、最初の値を破棄してシリアルを再確立する必要があります.現在の増分シーケンスは(-1)、長さは1です.
i=3の場合、2>1,2>−1である.したがって,最長の増分シーケンスは(1,2),(−1,2),長さは2であった.ここで,2の前が1であるか−1であるかは,後のインクリメントシーケンスを求めることに直接影響しない.(ただし、他の場合は影響する可能性があります)
このように推すと,我々は次のような結論を導いた.
ターゲット配列array[]の最初のi要素のうち、最長増分子シーケンスの長さはLIS[i]であると仮定する.では、
LIS[i+1]=max{1,LIS[k]+1}, array[i+1]>array[k], for any k <= i
すなわちarray[i+1]がarray[k]より大きい場合、i+1番目の要素はLIS[k]の長いサブシーケンスの後に接続されてより長いサブシーケンスを構成することができる.これと同時にarray[i+1]自体が少なくとも1つの長さのサブシーケンスを構成することができる.
上記の分析に基づいて、コードリストを得ることができます.
C++コード:
int Max(int *a, int n)
{
int max = a[0];
for(int i = 1; i < n; i++)
if(max < a[i])
max = a[i];
return max;
}
int LIS(vector &array)
{
int *a = new int[array.size()];
for(int i = 0; i < array.size(); i++)
{
a[i] = 1;//
for(int j = 0; j < i; j++) //
{
if(array [i] > array [j] && a[j] + 1 > a[i]) // j ，
{
a[i] = a[j] + 1;
}
}
}
return Max(a, array.size());
}
この方法の時間的複雑さはO(N 2＋N)＝O(N 2)である.
解法2前の解析では,i+1番目の元素を考察する際に,前のi個の元素の分布を考慮しない.次に,i+1番目の元素を考察する際に,前のi個の元素の場合を考慮する別の観点から解析する.
前のi個の要素のいずれかの増分サブシーケンスについて、このサブシーケンスの最大要素がarray[i+1]よりも小さい場合、array[i+1]をこのサブシーケンスの後に加算して、新しい増分サブシーケンスを構成することができる.
例えばi=4の場合、ターゲットシーケンスは1,−1,2,−3,4,−5,6,−7の最長インクリメントシーケンスは(1,2),(−1,2)である.
では,4>2であれば,4を直接前のサブシーケンスに増やして新しい増分サブシーケンスを形成することができる.
従って、array[i+1]よりも最大の要素が小さく、長さができるだけ長くなるように、前のi要素の1つの増分サブシーケンスを見つけたい.このようにarray[i+1]をインクリメンタルサブシーケンスに加算すると、array[i+1]を最大要素とする最長インクリメンタルサブシーケンスが見つかる.
配列の前のi個の要素のうちarray[i]を最大要素とする最長増分子シーケンスの長さはLIS[i]であると仮定する.
同時に、仮定:
長さ1の増分サブシーケンスの最大要素の最小値はMaxV[1]である.
長さ2の増分サブシーケンスの最大要素の最小値はMaxV[2]である.
……
長さLIS[i]の増分サブシーケンスの最大要素の最小値はMaxV[LIS[i]]である.
本サイクル不変式Pは、P:kがシーケンスa[0:i]の最長増分子シーケンスの長さであり、0≦i
P:0≤i＜n;kは、シーケンスa[0;i]の最長増分子シーケンスの長さである.
b[k]は、シーケンスa[0;i]のすべての長さkの増分サブシーケンスの最小終端要素値である.
従って、帰納仮定は、計算シーケンスa[0;i−1](i
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
template vector find_lis(vector &a)
{
vector b, p(a.size());//b k
// b[1]
//b
int u, v;
if (a.size() < 1)
return b;
b.push_back(0);
for (int i = 1; i < (int)a.size(); i++)
{
if (a[b.back()] < a[i])
{
p[i] = b.back();
b.push_back(i);
continue;
}
for (u = 0, v = b.size()-1; u < v;) //
{
int c = (u + v) / 2;
if (a[b[c]] < a[i])
u=c+1;
else v=c;
}
if (a[i] < a[b[u]])
{
if (u > 0)
p[i] = b[u-1];
b[u] = i;
}
}
for (u = b.size(), v = b.back(); u--; v = p[v])
b[u] = v;
return b;
}