我有这个用于查找最长递增子序列(LIS)的代码,但是当我测试我的代码时,我没有得到最大和,例如:
如果我输入 20 1 4 3 10 答案是 1 3 10,但我需要 1 4 10 这是我的 C 代码:
#include <stdio.h>
#include <stdlib.h>
#define INT_INF 1000
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() {
int size, i;
scanf(" %d", &size);
int A[size];
for(i = 0; i < size; i++){
scanf(" %d", &A[i]);
}
int tmp, lis_length = -1;
int *answer;
int LIS[size];
int index[size];
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;
}
第一个输入是数组中元素的数量。
我已经尝试过这篇文章:Find the Longest increasing Subsequence with the Maximum Sum和其他一些但没有成功。