题解 | #【模板】最长上升子序列#

#include <stdio.h>
// 二分查找
int binarySearch(int arr[], int l, int r, int target) {
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] < target) l = mid + 1;
        else r = mid;
    }
    return l;
}
int lengthOfLIS(int arr[], int n) {
    int tail[n]; // tail数组用于存储长度为i+1的子序列的末尾元素的最小值
    int len = 1; // 初始子序列长度为1
    tail[0] = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] < tail[0]) // 如果当前元素小于当前子序列中的最小值，则更新当前子序列的最小值
            tail[0] = arr[i];
        else if (arr[i] > tail[len - 1]) // 如果当前元素大于当前子序列中的最大值，则添加到当前子序列的末尾
            tail[len++] = arr[i];
        else // 如果当前元素在当前子序列中，使用二分查找找到比当前元素大的最小值，并进行替换
            tail[binarySearch(tail, 0, len - 1, arr[i])] = arr[i];
    }
    return len;
}
int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    printf("%d\n", lengthOfLIS(arr, n));
    return 0;
}