質問
入力:
n
(int
) とn
値(float
)間にランダムな値を持つ為替レート(それらの間で異なる)を表します4
と5
.出力: (同じ順序で)使用できる値の最大数を計算して、昇順と下降曲線を表しますか?
EX 8つの値
4.5 4.6 4.3 4.0 4.8 4.4 4.7 4.1
出力する必要があります
5 (4.5 4.6 4.8 4.4 4.1)
私のアプローチ
- 連続して試してみると
if
s、曲線状態を尊重するが、最長ではないランダムな配列を取得します。 - 私はそれに精通していないので、バックトラッキングを試みていませんが、それを使用してすべてのソリューションを計算して、最長のソリューションを選択しなければならないことを教えてくれます。
- そして最後に:ブルートフォースですが、アルゴリズム設計の割り当てであるため。私もそれを渡さないかもしれません。:)
よりシンプル/より効率的/高速な方法はありますか?
Daniel Lemireのアルゴリズムに基づいた私の試みは次のとおりです。ポジション0、i、およびNは考慮されていないようです。 IFSが問題であると確信していますが、どうすれば修正できますか?
for(int i = 0; i<n-1; i++){
int countp=0; // count ascending
int countn=0; // count descending
for(int j=0;j<=i;j++){
if(currency[j]<currency[j+1]){
countp++;
System.out.print(j+" ");
}
}
System.out.print("|| ");
for(int j=i;j<n-1;j++){
if(currency[j]>currency[j+1]){
countn++;
System.out.print(j+" ");
}
}
System.out.println();
if(countn+countp>maxcount) maxcount=countn+countp;
}
解決
まず、ある時点から別のポイントに最長の単調サブシーケンスを計算できるようにしたいと考えています。 (それが増加しているか減少しているかどうかは、問題にあまり影響しません。)これを行うには、動的プログラミングを使用できます。たとえば、インデックス0からIの場合、問題を解決するには、0から0(些細な!)、0から1、次に0から2までの問題を解決することから始めます。配列)あなたの最良のソリューション。
たとえば、Pythonには、インデックス0からインデックスiに移動する最長の非脱落シーケンスを計算するコードがあります。アレイ(BBEST)を使用して、0から0からIまでのすべてのJのソリューションを0からjに保存します。つまり、最長の非減少サブシーケンスの長さは0からjまでです。 (使用される戦略は動的プログラミングです。)
def countasc(array,i):
mmin = array[0] # must start with mmin
mmax= array[i] # must end with mmax
bbest=[1] # going from 0 to 0 the best we can do is length 1
for j in range(1,i+1): # j goes from 1 to i
if(array[j]>mmax):
bbest.append(0) # can't be used
continue
best = 0 # store best result
for k in range(j-1,-1,-1): # count backward from j-1 to 0
if(array[k]>array[j]) :
continue # can't be used
if(bbest[k]+1>best):
best = bbest[k]+1
bbest.append(best)
return bbest[-1] # return last value of array bbest
またはJavaで同等に(リクエストによって提供):
int countasc(float[] array,int i) {
float mmin = array[0];
float mmax = array[i];
ArrayList<Integer> bbest= new ArrayList<Integer>();
bbest.add(1);
for (int j = 1; j<=i;++j) {
if(array[j]>mmax){
bbest.add(0);
continue;
}
int best = 0;
for(int k = j-1; k>=0;--k) {
if(array[k]>array[j])
continue;
if(bbest.get(k).intValue()+1>best)
best = bbest.get(k).intValue()+1;
}
bbest.add(best);
}
return bbest.get(bbest.size()-1);
}
同じタイプの関数を記述して、IからN-1までの最長の非増加シーケンスを見つけることができます(演習として残されます)。
Countascは線形時間で実行されることに注意してください。
これで、実際の問題を解決できます。
Start with S, an empty array
For i an index that goes from 0 to n-1 :
compute the length of the longest increasing subsequence from 0 to i (see function countasc above)
compute the length of the longest decreasing subsequence from n-1 to i
add these two numbers, add the sum to S
return the max of S
それは二次的な複雑さを持っています。このソリューションを改善できると確信しています。このアプローチには多くの冗長性があります。たとえば、スピードの場合、おそらく、非初期化アレイBBESTでCountascを繰り返し呼び出すべきではありません。1回計算できます。おそらく、いくつかの作業でO(n log n)に複雑さを抑えることができます。
他のヒント
最初のステップは、関連を解決する方法を理解することです 最長のサブシーケンス 問題。この問題には、aがあります 単純なアルゴリズム あれは O(n^2)
ただし 最適アルゴリズム は O(n log n)
. 。これらのアルゴリズムを理解することで、ソリューションの正しい軌道に乗ることができます。