LISnlogn写法

tech2025-07-11  2

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; }

参考博客

Junior Dynamic Programming——动态规划初步·各种子序列问题
最新回复(0)