C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2022-04-05

class Solution {
public:
    int dp[1005]={0};//dp[i]存储的长度为i+1的尽可能小的值
    int LIS(vector<int>& arr) {
        int n=arr.size();
        if(n==0)
            return 0;
        int len=0;//初始化
        dp[len++]=arr[0];//初始化
        for(int i=1;i<n;i++){//遍历每个arr[i]
            if(arr[i]>dp[len-1]){//如果严格大于dp[]的最后一个数，则加入dp[]
                dp[len++]=arr[i];
            }else{//否则，二分找到dp[]中>=arr[i]的数，并用arr[i]替换
                int l=0,r=len-1,mid;
                while(l<r){
                    mid=(l+r)>>1;
                    if(dp[mid]>=arr[i]){
                        r=mid;
                    }else{
                        l=mid+1;
                    }
                }
                dp[l]=arr[i];//替换
            }
        }
        return len;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2021-12-01

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
        int LIS(vector<int>& arr) {
        // write code here
        vector<int>res;
        int len = arr.size();
        for(int i=0;i<len;i++){
            if(res.size() == 0 || res.back() < arr[i]){
                res.push_back(arr[i]);
            }else{
                int j = res.size()-2;
                while(j>=0){
                    if(arr[i] > res[j])break;
                    j--;
                }
                res[j+1] = arr[i];
            }
        }
        return res.size();
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-07-22

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& nums) {
        // write code here
        if (nums.empty()) {
              return 0;
          }
          vector<int> dp(nums.size(), 0);
          int len = 0;
          dp[len] = nums[0];
          for (int i = 1; i < nums.size(); ++i) {
              if (nums[i] > dp[len]) {
                  dp[++len] = nums[i];
              } else {
                  int ll = 0, rr = len, pos = -1;
                  while (ll <= rr) {
                      int mid = ll + (rr - ll) / 2;
                      if (dp[mid] < nums[i]) {
                          pos = mid;
                          ll = mid + 1;
                      } else {
                          rr = mid - 1;
                      }
                  }
                  dp[pos + 1] = nums[i];
              }
          }
          return len + 1;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-03-20

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& arr) {
        // write code here
        vector<int> res;
        for(int i = 0; i < arr.size(); i++){
            if(res.size() == 0 || res.back() < arr[i]) res.push_back(arr[i]);
            else res[binary_search(res,  arr[i])] = arr[i];
        }
        return res.size();
    }
    int binary_search(vector<int>& arr, int val){
        int l = 0, r = arr.size()-1, mid;
        while(l <= r){
            mid = (l + r) / 2;
            if(arr[mid] <= val) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-01-20

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& arr) {
        // write code here
        vector<int> res;
        for(auto& a:arr){
            auto iter=lower_bound(res.begin(), res.end(), a);
            if(iter==res.end())
                res.push_back(a);
            else
                *iter=a;
        }
        return res.size();
    }
};