6

ソートされていない配列があり、ソートされた要素の最長シーケンスを抽出する必要があります。例えば

A = 2,4,1,7,4,5,0,8,65,4,2,34

ここで 0,8,65 は私のターゲットシーケンスです

このシーケンスが始まるインデックスを追跡する必要があります

4

3 に答える 3

7

O(N)このアルゴリズムを使用すると、線形時間でそれを行うことができます。元のベクトルlenと同じサイズのベクトルを作成します。これには、要素が属する最長の連続した昇順の実行の長さが含まれます。Nlen[i]seq[i]

の値はlen[i]次のように計算できます。

len[0] = 1;
for (int i = 1 ; i != N ; i++) {
    len[i] = seq[i-1] >= seq[i] ? 1 : len[i-1]+1;
}

手に持って、要素lenのインデックスを見つけますmax(len)。これは、実行の最後の要素です。に戻ってlen[j] == 1、実行の最初の要素を見つけます。

seq    len
---    ---
  2      1
  4      2
  1      1
  7      2
  4      1
  5      2
  0      1
  8      2
 65      3 << MAX
  4      1
  2      1
 34      2

len[i-1]アルゴリズムの各ステップでは、計算する要素のみが必要であるため、前の、、、およびのベクトル表現を削除して保持することによりlen、定数空間を最適化できることに注意してください。lenmax_lenmax_len_index

これは、一定のスペース用に最適化されたこのアルゴリズムです。変数は線形空間アルゴリズムからlen表します。len[i-1]

int len = 1, pos = 0, maxlen = 1, current_start = 0;
for (int i = 1 ; i < seq.size() ; i++) {
    if (seq[i] > seq[i-1]) {
        len++;
        if (len > maxlen) {
            maxlen = len;
            pos = current_start;
        }
    } else {
        len = 1;
        current_start = i;
    }
}

これがideoneのこのプログラムへのリンクです。

于 2012-08-19T12:17:33.437 に答える
5

4 つのインデックス (begin、end、tmp_begin、tmp_end) が必要です。tmp_beginを作業インデックスとして使用して元の配列を反復処理し、より長い並べ替えられたシーケンスの更新とインデックスtmp_endを見つけるたびに繰り返します。beginend

サブシーケンスがソートされていることを確認するには、サブシーケンス内の連続するアイテムの各ペアについて、i の要素が i-- の要素より大きいことを確認する必要があります。

最後に: 元の配列の で始まり でbegin終わるすべての要素を出力しendます。

于 2012-08-19T12:16:57.067 に答える
1 
for(int i=0;i<size_of_array;i++)
{
  iterate++;
  after=array[iterate];
  if(after>before) {current_counter++;} else {current_counter=0;}
  if(max_counter<current_counter) max_counter=current_counter;
  before=array[iterate];
}

printf(" maximum length=%i ",max_counter);
于 2012-08-19T12:16:03.543 に答える