描述:
7
1 7 3 5 9 4 8
输出4
最长递增子序列为1 3 5 9,不必连续。
解法:
三种思路:
转化为最长公共子序列(n^2),动态规划(n^2),不知叫什么解法(nlogn)。
解法一:转化
先排序nlogn,在最长公共子序列
解法二:动态规划
dp[i]定义为,以此数为终点的最长递增子序列,
则dp[i] = dp[j] + 1,且dp <- max(dp[0] .. dp[i - 1]), a[i] > a[j]
注意处理边界条件,如果不存在dp[i],则赋值为1,得:
#include <iostream>
using namespace std; int main()
{
int n;
cin >> n;
int* arr = new int[n]();
int* arr_data = new int[n](); for (int i = ; i < n; ++i) {
int more;
cin >> more;
arr_data[i] = more;
if (i == ) {
arr[] = ;
continue;
} int big = ;
for (int j = ; j < i; ++j) {
if (arr_data[j] < more && big < arr[j] + )
big = arr[j] + ;
}
arr[i] = big;
} int ma = arr[];
for (int i = ; i < n; ++i)
if (ma < arr[i])
ma = arr[i]; cout << ma << endl;
return ;
}
解法三:更快解法
维护一个数组,第一个元素储存长度为1的递增序列最小值,第二个元素储存长度为2的递增序列终点的最小值。。。数组长度即为最长。
做法:
每次插入,替换恰大于插入数的数,如果没有,否则直接插在后面。
如例子:
1
1 7
1 3
1 3 5
1 3 5 9
1 3 4 9
1 3 4 8
以上为每次插入后,数组的变化。注意,最后数组并不是最长递增子序列!
由于每次使用二分查找插入,所以时间复杂度是nlogn。