贝壳第三题

#include<iostream> #include<vector> using namespace std; void lengthOfLIS(vector<long int>& nums) { long int maxres = 1; int n = nums.size(); if (n == 0) return; vector<long int> res(n, 1); for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++)  if (nums[i] > nums[j]) res[i] = max(res[i], res[j] + 1); maxres = max(maxres, res[i]); } cout << maxres << endl; } int main() { int n; vector<long int >vec; while (cin >> n) { long int a = 0; for (int i = 0; i < n; i++) { cin >> a; vec.push_back(a); } lengthOfLIS(vec); } return 0; }

这种DP超时，卡时间了。

Python 的 dp只能过36%，c++的dp可以过这么多。

因为算法复杂度不是nlogn

要用二叉搜索