最长上升子序列 - DP O(n*n)
F[t] 表示从 1 到t这一段中以 t 结尾的最长上升子序列的长度
F[t] = max{1, F[j] + 1} (j = 1, 2, ..., t - 1, 且A[j] < A[t])
根据F[]的值进行分类。对于F[]的每一个取值k，我们只需要保留满足F[t] = k的所有A[t]中的最小值。设D[k]记录这个值，即D[k] = min{A[t]} (F[t] = k)。
F[t] 表示从 1 到t这一段中以 t 结尾的最长上升子序列的长度
F[t] = max{1, F[j] + 1} (j = 1, 2, ..., t - 1, 且A[j] < A[t])
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <map>
#include <set>
#include <iterator>
#include <algorithm>
#include <functional>
#include <utility>
#include <sstream>
#include <climits>
#include <cassert>
#define BUG puts("here!!!");using namespace std;
const int N = 100005;
int data[N];
int dp[N];
int main() {int n;while(cin >> n) {for(int i = 1; i <= n; i++) {scanf("%d", &data[i]);}memset(dp, 0, sizeof(dp));for(int i = 1; i <= n; i++) {dp[i] = 1;}int mmax = 0;if(n > 0) mmax = 1;for(int i = 2; i <= n; i++) {for(int j = 1; j < i; j++) {if(data[j] < data[i]) {dp[i] = max(dp[i], dp[j] + 1);}}mmax = max(mmax, dp[i]);}printf("%d\n", mmax);}return 0;
}
注意到D[]的两个特点：
(1) D[k]的值是在整个计算过程中是单调不上升的。
(2) D[]的值是有序的，即D[1] < D[2] < D[3] < ... < D[n]。
利用D[]，我们可以得到另外一种计算最长上升子序列长度的方法。设当前已经求出的最长上升子序列长度为len。先判断A[t]与D[len]。若A[t] > D[len]，则将A[t]接在D[len]后将得到一个更长的上升子序列，len = len + 1， D[len] = A[t]；否则，在D[1]..D[len]中，找到最大的j，满足D[j] < A[t]。令k = j + 1，则有D[j] < A[t] <= D[k]，将A[t]接在D[j]后将得到一个更长的上升子序列，同时更新D[k] = A[t]。最后，len即为所要求的最长上升子序列的长度。
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <map>
#include <set>
#include <iterator>
#include <algorithm>
#include <functional>
#include <utility>
#include <sstream>
#include <climits>
#include <cassert>
#define BUG puts("here!!!");using namespace std;
const int N = 100005;
int num, D[N];
int main() {int n;while(cin >> n) {D[0] = -1;int top = 0;for(int i = 1; i <= n; i++) {scanf("%d", &num);if(num > D[top]) {top++;D[top] = num;}else {int low = 1, high = top;while(low <= high) {int mid = (low+high) >> 1;if(num > D[mid]) {low = mid + 1;}else high = mid - 1;}D[low] = num;}}printf("%d\n", top);}return 0;
}