class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // 辅助空间 在计算过程中保持严格单增
        // tail[i] = 长度为i的上升子序列的最小末尾 
        vector<int> tail(nums.size() + 1, INT_MIN);
        int max_length = 0; // 已知最长上升子序列长度

        for(int i = 0; i < nums.size(); i++){
            if(nums[i] > tail[max_length]){
                // 如果num[i]严格大于所有tail，则追加
                // 在计算过程中保持严格单增
                // 即最长上升子序列+1，并以num[i]结尾
                tail[++max_length] = nums[i];
            }else{
                // 使用二分搜索定位第一个大于num[i]的tail
                int l = 0, r = max_length;
                int mid = 0;
                while(l < r){
                    mid = (l + r) / 2;
                    if(tail[mid] == nums[i]){
                        // 当tail中含有相等num[i]的元素时不能进行替换操作
                        mid = -1;
                        break;
                    }else if(tail[mid] < nums[i]){
                        l = mid + 1;
                    }else{
                        r = mid - 1;
                    }
                }
                if(mid != -1){
                    // 替换(缩小)第一个大于num[i]的上升子序列的最小末尾
                    // 此处即使不进行if-else判断也可以通过LeetCode
                    // 但是这样并没有保证每次换掉的是第一个更大的
                    // tail序列将会不同，但长度不变
                    // 可能的猜想：
                    // 1. 算法可以优化，可能不需要保存所有之前更短的状态
                    // 2. LeetCode判例不足
                    // if(tail[l] > nums[i])
                        tail[l] = nums[i];
                    // else
                    //     tail[l+1] = nums[i];
                }
            }
            // for(int q = 1; q <= max_length; q++){
            //     cout<<tail[q]<<" ";
            // }
            // cout<<endl;
        }

        // 最终tail的长度即为最长上升子序列长度
        return max_length;
    }
};