LIS的O(nlogn)算法中关于二分查找的问题

Question

用O(nlogn)算法 求最长上升子序列 和最长不下降子序列 中用到的二分搜索，是查找第一个 >= a[i] 的元素的下标还是第一个 > a[i] 的元素的下标？

Answer 1

在 LIS 算法中，通常使用二分查找来查找第一个大于等于 a[i] 的元素的下标。

• 这是因为，LIS 算法中所求的是最长上升子序列，也就是说，每一个元素都应该比它前面的元素要大。如果使用第一个大于 a[i] 的元素的下标，那么就可能会出现一个元素和它前面的元素相等的情况，这样就不能满足 LIS 的要求了。
• 另一方面，如果要求最长不下降子序列，那么就可以使用第一个大于 a[i] 的元素的下标，因为最长不下降子序列中的元素是可以相等的。
• 简单来说，在 LIS 算法中，用二分查找查找第一个大于等于 a[i] 的元素的下标，是为了保证 LIS 中的每一个元素都比它前面的元素要大。如果你想要求最长不下降子序列，就可以使用第一个大于 a[i] 的元素的下标。

#include <stdio.h>
#include <stdlib.h>

#define max(a, b) ((a) > (b) ? (a) : (b))

int n;
int a[100005];
int b[100005];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    int len = 0;
    for (int i = 1; i <= n; i++)
    {
        int left = 1, right = len;
        while (left <= right)
        {
            int mid = (left + right) / 2;
            if (b[mid] < a[i])
                left = mid + 1;
            else
                right = mid - 1;
        }
        b[left] = a[i];
        if (left > len)
            len = left;
    }

    printf("%d\n", len);

    return 0;
}