最長上升子序列 II
題目描述
給定一個長度為 N 的數列，求數值嚴格單調遞增的子序列的長度最長是多少，
輸入格式
第一行包含整數 N，
第二行包含 N 個整數，表示完整序列，
輸出格式
輸出一個整數，表示最大長度，
資料范圍
1 ≤ N ≤100000
-10^9 ≤ 數列中的數 ≤ 10^9
輸入樣例：
7
3 1 2 1 8 5 6
輸出樣例：
4
演算法1
(DP) O(n^2)
動態規劃狀態轉移
時間復雜度
O(n^2)，資料范圍10^5會TLE
空間復雜度
dont know
C++ 代碼
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int a[N];
int f[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
a[0] = - 1e9;
for(int i = 1; i <= n; i ++)
for(int j = 0; j < i; j ++)
if(a[j] < a[i])
f[i] = max(f[i], f[j] + 1);
int res = -1;
for(int i = 1; i <= n; i ++) res = max(res, f[i]);
cout << res;
return 0;
}
演算法2
(利用單調堆疊的思路優化) O(nlogn)
貪心思路：較小的數作為的子序列結尾 比 較大的數子序列的結尾 更好
q[i]存的是長度為i的上升子序列的第i位的值，
列舉時查看當前元素a[i]能夠插入到哪個子序列的末尾，根據貪心想法插入的一定是子序列結尾元素q[i]嚴格小于當前元素a[i]的子序列，
時間復雜度
二分logn,列舉n 時間復雜度nlogn
空間復雜度
dont know
C++ 代碼
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int a[N], q[N];
int f[N];
int main()
{
cin >> n;
for(int i = 0; i < n; i ++) cin >> a[i];
int len = 0;
for(int i = 0; i < n; i ++)
{
int l = 0, r = len;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid] < a[i]) l = mid;
else r = mid - 1;
}
len = max(len, r + 1);
q[r + 1] = a[i];
}
cout << len;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/548838.html
標籤：其他