10 9 2 5 3 7 101 18

4

0 1 0 3 2 3

4

7 7 7 7 7 7 7

1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    // 求最长严格递增子序列的长度
    int lengthOfLIS(vector<int>& nums) {
        // dp 数组，用于保存长度为 $i+1$ 的递增子序列最后一个元素的最小值
        vector<int> dp;
        for (int num : nums) {
            // 使用二分查找在 dp 中找到第一个大于或等于 num 的位置
            auto it = lower_bound(dp.begin(), dp.end(), num);
            if (it == dp.end()) {
                // 如果没有找到，则将 num 加入到 dp 的末尾
                dp.push_back(num);
            } else {
                // 找到则用 num 替换当前元素
                *it = num;
            }
        }
        // dp 的长度即为最长严格递增子序列的长度
        return dp.size();
    }
};

int main() {
    vector<int> nums;
    int x;
    // 读入所有整数，输入以空格隔开
    while (cin >> x) {
        nums.push_back(x);
    }
    Solution sol;
    int ans = sol.lengthOfLIS(nums);
    cout << ans << endl;
    return 0;
}

# 定义 Solution 类
class Solution:
    def lengthOfLIS(self, nums: list) -> int:
        # dp 列表用于保存长度为 $i+1$ 的递增子序列最后一个元素的最小值
        dp = []
        # 遍历每个数字
        for num in nums:
            # 使用二分查找找到 dp 中第一个大于或等于 num 的位置
            left, right = 0, len(dp)
            while left < right:
                mid = (left + right) // 2
                if dp[mid] < num:
                    left = mid + 1
                else:
                    right = mid
            # 如果 left 等于 dp 长度，则说明 num 大于所有元素
            if left == len(dp):
                dp.append(num)
            else:
                # 否则用 num 替换找到的位置上的元素
                dp[left] = num
        # dp 的长度即为最长严格递增子序列的长度
        return len(dp)

if __name__ == "__main__":
    import sys
    # 读入所有输入，假设输入数字以空格隔开
    data = sys.stdin.read().strip().split()
    nums = list(map(int, data))
    sol = Solution()
    print(sol.lengthOfLIS(nums))

import java.util.*;
import java.io.*;

public class Main {
    // 定义 Solution 类
    static class Solution {
        // 求最长严格递增子序列的长度
        public int lengthOfLIS(int[] nums) {
            // dp 数组用于保存长度为 $i+1$ 的递增子序列最后一个元素的最小值
            ArrayList<Integer> dp = new ArrayList<>();
            for (int num : nums) {
                // 二分查找在 dp 中寻找第一个大于或等于 num 的位置
                int left = 0, right = dp.size();
                while (left < right) {
                    int mid = (left + right) / 2;
                    if (dp.get(mid) < num) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                // 如果 left 等于 dp 的长度，则将 num 添加到末尾
                if (left == dp.size()) {
                    dp.add(num);
                } else {
                    // 否则用 num 替换 dp 中对应位置的元素
                    dp.set(left, num);
                }
            }
            // dp 的长度即为最长严格递增子序列的长度
            return dp.size();
        }
    }

    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 读入输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        // 使用空格分割输入的字符串
        String[] parts = line.trim().split("\\s+");
        int n = parts.length;
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(parts[i]);
        }
        Solution sol = new Solution();
        int ans = sol.lengthOfLIS(nums);
        // 输出结果
        System.out.println(ans);
    }
}