1

数値が循環的に配置されている場合、最長増加サブシーケンスの長さを見つけるにはどうすればよいですか。例えば：

LIS of 3, 2, 1 is 3 [1, 2, 3].

PS O(nlogn) で Linear LIS を解く方法を知っています。

問題のソース: https://www.codechef.com/problems/D2/

更新: LIS は、円を 1 回だけ通過して計算する必要があります。例 2:LIS of 1, 4, 3は 2 で、1, 3 または1, 4またはのいずれか3, 4です。
ありがとう

4

1 に答える 1

0

問題の例は間違っています。[1,2,3] の円回転は [2,3,1] または [3,1,2] になります。

その場合、最長増加部分列と同じように解くことができます。として：

  1. リストを昇順に並べ替えます。

  2. 元のリストで最小要素を見つけます。

  3. 元のリストの min_index から反復を開始し、ソートされたリストと比較して、最長共通部分列と同じ論理で中間配列 L[i][j] を作成します。i は min_index から (i+n-1)%n まで変化します
  4. 最後に L[max_index][n] を返します
于 2016-10-18T05:46:14.963 に答える