3

入力: n ( int) とn値 ( float) は、 と の間のランダムな値で為替レート (それらの間で異なります) を表し4ます5。

出力:上昇曲線と下降曲線を表すために (同じ順序で) 使用できる値の最大数を計算しますか?

ex 八つの価値観

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)

私のアプローチ

  • 連続したifs を試すと、曲線条件を尊重するランダムな配列が得られますが、最長ではありません。
  • 私はそれに慣れていないのでバックトラックを試みていませんが、それを使ってすべての解を計算し、最も長いものを選ぶ必要があると何かが教えてくれます。
  • そして最後に、ブルートフォースですが、これはアルゴリズム設計の課題であるためです。私はそれを手渡さないかもしれません。:)

よりシンプル/より効率的/高速な方法はありますか?

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;                   
        }
4

2 に答える 2

3

まず、ある点から別の点への最長の単調部分列を計算できるようにする必要があります。(増加しているのか減少しているのかは、問題にはあまり影響しません。) これを行うには、動的計画法を使用できます。たとえば、0 から i までのインデックスが与えられた問題を解くには、問題を 0 から 0 に解くことから始めます (簡単なことです!)。配列）あなたの最善の解決策。

たとえば、インデックス 0 からインデックス i までの最長の非減少シーケンスを計算する Python のコードを次に示します。配列 (bbest) を使用して、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) に下げることができます。

于 2011-12-02T02:37:38.127 に答える
1

最初のステップは、関連する最長増加部分列の問題を解決する方法を理解することです。この問題には、単純なアルゴリズムがありO(n^2)ますが、最適なアルゴリズムはO(n log n)です。これらのアルゴリズムを理解することで、ソリューションへの正しい軌道に乗ることができます。

于 2011-12-02T02:08:11.417 に答える