LIS可以用dp解决。
下面给出两种简单的dp写法：
代码1：
long long a[100010]; long long dp[100010]; //dp[i]表示'以a[i]结尾'的子序列中的最长上升子序列长度 int main() { long long n, ans = 0; scanf("%lld", &n); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); for (int i = 1; i <= n; i++) { for (int j = 1; j < i; j++) if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1); ans = max(ans, dp[i] + 1); } printf("%lld\n", ans); return 0; }代码2：
long long a[100010]; long long dp[100010]; //dp[i]表示'以a[i]开头'的子序列中的最长上升子序列长度 int main() { long long n, ans = 0; scanf("%lld", &n); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); for (int i = n; i >= 1; i--) for (int j = 1; j < i; j++) if (a[j] < a[i]) { dp[j] = max(dp[j], dp[i] + 1); ans = max(ans, dp[j] + 1); } printf("%lld\n", ans); return 0; }不过dp的时间复杂度显然是 O ( n 2 ) O(n^2) O(n2)，我们可以用贪心的思想优化到 O ( n l o g n ) O(nlogn) O(nlogn)。
原理基础：
1.我们定义一个f[]数组，其中f[i]记录长度为len的最长上升子序列的最后一个数。
2.显然，当一个最长上升子序列长度确定时，我们总是希望最后一个元素尽可能小，这样我们更有可能在后面继续插入元素。
3.由于是求最长上升子序列，设y=f[i]，其中随着i的增大，y肯定会增大，因此f数组是一个满足单调性的数组，所以我们可以用二分，这也是 O ( n l o g n ) O(nlogn) O(nlogn)时间复杂度的保障。
具体代码实现看代码以及注释：
long long a[100010]; long long f[100010]; int main() { long long n, ans = 0; scanf("%lld", &n); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); long long len = 1; //表示最长子序列的长度，也是f的最大下标 f[len] = a[1]; //f[1]=a[1]表示当前最长上升子序列是长度为1、以a[1]结尾的子序列 for (int i = 2; i <= n; i++) { if (a[i] > f[len]) //如果a[i]>f[len]，那么我们可以加到最后面，这样可以最长上升子序列可以+1 f[++len] = a[i]; else { long long l = 1, r = len, pos; //二分f数组下标 /* ***二分的目的是找到一个最大的mid 使得f[mid]<a[i],然后再把f[mid+1]更新成a[i]*** 因为找到了f[mid]<a[i]，那么有f[mid+1]>=a[i], 我们就可以把f[mid+1]更新到a[i]，遵循上面的原理基础2。 当然，二分的时候我们并没有去找mid，而是直接找到mid+1 也就是找最小的mid满足f[mid]>=a[i] */ while (l <= r) { long long mid = l + r >> 1; if (f[mid] >= a[i]) { pos = mid; r = mid - 1; } else { l = mid + 1; } } f[pos] = a[i]; } } printf("%lld\n", len); return 0; }