3

通常の関数と再帰関数で LIS の長さを出力できます。しかし、C++ の特定の配列にある LIS サブシーケンスのインデックスを出力したいと考えています。

LIS の長さを見つける関数は次のとおりです。

int lis( int *arr, int n )
{
   int *lis, i, j, max = 0;
   lis = (int*) malloc ( sizeof( int ) * n );
   for ( i = 0; i < n; i++ )
      lis[i] = 1;
   for ( i = 1; i < n; i++ )
      for ( j = 0; j < i; j++ )
         if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
            lis[i] = lis[j] + 1;
   for ( i = 0; i < n; i++ )
      if ( max < lis[i] )
         max = lis[i];
   /* Free memory to avoid memory leak */
   free( lis );
   return max;
}

ここarray[10]={7 6 2 3 4 1 8 5 9 10}

ここLIS Length=6

数字のインデックスを印刷したい{2 3 4 6 8 9}（配列インデックスのシーケンスではなく、印刷したいもの）シーケンスのインデックスarray[10]

4

7 に答える 7

11

各インデックスの lis を計算した後、max に等しい tmp 値を取り、lis 配列を逆方向に移動し、max に等しい要素を見つけるたびに、そのインデックスを答えに追加し、tmp を減らします。これにより、インデックス配列が逆順で取得されます。

コード例:

int tmp = max;
std::vector<int> indexes;
for( i = n - 1; i >= 0; --i )
   if( lis[ i ] == tmp )
   {
      indexes.push_back( i );
      --tmp;
   }
std::reverse( indexes.begin(), indexes.end());
于 2013-02-11T07:44:15.163 に答える
1

順番に印刷するには、再帰的アプローチを使用できます: 呼び出し: printLIS(lis, lis.length -1, arr, max)

public static void printLIS(int[] lis, int lisIndex, int[] arr, int max) {
    if(max == 0) {
        return;
    }
    if(lis[lisIndex] == max) {
        printLis(lis,lisIndex-1, arr, max-1);
        System.out.print(arr[lisIndex] + " ");
    } else {
        printLis(lis,lisIndex-1, arr, max);
    }

}
于 2014-02-19T21:17:26.453 に答える
1 
void solution() {
  int n;
  cin >> n;
  vector<int> v(n);
  for (int &x : v) cin >> x;
  vector<int> dp(n, 1);
  int i = 0, j = 1;
  vector<int> par(n);
  for (int i = 0; i < n; i++) {
     par[i] = i;
  }
  for (int j = 1; j < n; j++) {
     for (int i = 0; i < j; i++) {
        if (v[j] > v[i] && dp[j] < dp[i] + 1) {
           dp[j] = dp[i] + 1;
           par[j] = i;
        }
     }
  }
  int mx = 1, idx = 0;
  for (int i = 0; i < n; i++) {
     if (dp[i] > mx) {
        mx = dp[i];
        idx = i;
     }
  }
  cout << mx << "\n";
  vector<int> seq;
  while (true) {
     seq.pb(v[idx]);
     if (par[idx] == idx) break;
     idx = par[idx];
  }
  reverse(seq.begin(), seq.end());
  for (int i = 0; i < mx; i++) {
     cout << seq[i] << " ";
  }
}

親配列を維持し、親 [index] = index であるインデックスに到達するまで、LIS が親ごとに終了するインデックスから逆方向に移動します。

于 2020-07-20T16:12:37.770 に答える