特定のリストの最長増加サブシーケンスを形成する要素を見つけようとして問題が発生しています。
リストの特定の項目の値を見つけるアルゴリズムがあり、それが使用する方法を理解しています。LIS を構成する数値を取得するために、何をどこに追加すればよいかわかりません。
これが私が今していることです：
for (A[0] = N[0], i=lis=1; i<n; i++) {
int *l = lower_bound(A, A+lis, N[i]);
lis = max(lis, (l-A)+1);
*l = N[i];
}
Aは部分 LIS を格納する配列ですが、別の解が存在する可能性があるため、ある時点で変更されます。N要素の配列です。
ここから の最長増加サブシーケンスを見つけるにはどうすればよいNですか?
追加の 2 つの配列を使用して、LIS を見つけることができます。たとえば、ソースが配列Aに配置されている場合
1 8 4 12 6 6 1
また、LIS の要素である可能性が高いAの要素を格納するための配列Bがあります。より正確には、Bは位置iで LIS として維持されます。さらに、位置を記録するための配列idx 。
A[0]から始めて、 A[ 0] を B[0] に配置します。A[0] はBの位置 0 に追加されるため、idx[0] = 0 です。
[0] 1 2 3 4 5 6
A | 1 8 4 12 6 6 1
B | (1)
idx | 0
次に、位置 1 については、Bの要素が A[1] より小さいため、A[1] が B に追加されます。idx[1] は、Bの位置を 1 として記録します。
0 [1] 2 3 4 5 6
A | 1 8 4 12 6 6 1
B | 1 (8)
idx | 0 1
位置 2、A[2]、または 4 については、 Bを LIS として維持するために、 Bの要素と比較して LIS の要素である可能性が高くなります。したがって、Bで 4 以上の最小の要素を見つけて 8 に置き換えます。 idx[2] は、Bで 8 が置き換えられる位置に設定されます。検索アルゴリズムを使用して、そのような要素を見つけることができると思います。
0 1 [2] 3 4 5 6
A | 1 8 4 12 6 6 1
B | 1 (4)
idx | 0 1 1
このように続けて、徐々にidxを設定していきます。
position 3
0 1 2 [3] 4 5 6
A | 1 8 4 12 6 6 1
B | 1 4 (12)
idx | 0 1 1 2
position 4
0 1 2 3 [4] 5 6
A | 1 8 4 12 6 6 1
B | 1 4 (6)
idx | 0 1 1 2 2
position 5
0 1 2 3 4 [5] 6
A | 1 8 4 12 6 6 1
B | 1 4 (6)
idx | 0 1 1 2 2 2
position 6
0 1 2 3 4 5 [6]
A | 1 8 4 12 6 6 1
B | (1) 4 6
idx | 0 1 1 2 2 2 0
idxに記録された位置があり、 idxを逆方向にスキャンして LIS を見つけます。
0 1 2 3 4 5 6
A | 1 8 4 12 6 6 1
idx | 0 1 1 2 2 (2) 0 | 6
0 1 2 3 4 5 6
A | 1 8 4 12 6 6 1
idx | 0 1 (1) 2 2 2 0 | 4 6
0 1 2 3 4 5 6
A | 1 8 4 12 6 6 1
idx | (0) 1 1 2 2 2 0 | 1 4 6
したがって、出力 LIS は {1, 4, 6} です。
ソースとしてのコードと A = {1, 8, 4, 12, 6, 6, 1}
#include <stdio.h>
#include <stdlib.h>
#define INT_INF 10000
int search_replace(int *lis, int left, int right, int key) {
int mid;
for (mid = (left+right)/2; left <= right; mid = (left+right)/2) {
if (lis[mid] > key) {
right = mid - 1;
} else if (lis[mid] == key) {
return mid;
} else if (mid+1 <= right && lis[mid+1] >= key) {
lis[mid+1] = key;
return mid+1;
} else {
left = mid + 1;
}
}
if (mid == left) {
lis[mid] = key;
return mid;
}
lis[mid+1] = key;
return mid+1;
}
int main(void) {
int i, tmp, size = 7, lis_length = -1;
int *answer;
int A[7] = {1,8,4,12,6,6,1},
LIS[7],
index[7] = {0};
LIS[0] = A[0];
for (i = 1; i < size; ++i) {
LIS[i] = INT_INF;
}
for (i = 1; i < size; ++i) {
index[i] = search_replace(LIS, 0, i, A[i]);
if (lis_length < index[i]) {
lis_length = index[i];
}
}
answer = (int*) malloc((lis_length+1) * sizeof(int));
for (i = size-1, tmp = lis_length; i >= 0; --i) {
if (index[i] == tmp) {
answer[tmp] = A[i];
--tmp;
}
}
printf("LIS: ");
for (i = 0; i < lis_length+1; ++i) {
printf("%d ", answer[i]);
}
printf("\n");
return 0;
}
そして、コードの出力
LIS: 1 4 6