问题描述
你有个同学叫小明，他早听闻祖国河山秀丽，于是有一个爬山的计划，并列了一张所有山的高度表，而又因“人往高处走”的说法，所以他希望爬的每一座山都比前一座要高，并且不能改变山的高度表上的顺序，爬的山数还要最多，请贵系的你帮他解决这个问题。
输入格式
输入第一行为num，代表山的个数
输入第二行有num个整数，代表每座山的高度
输出格式
输出只有一个数，为符合要求的最大爬山数
样例输入
10
1 3 5 7 9 2 4 6 8 10
样例输出
6
样例输入
10
1 3 2 7 5 4 5 6 10 11
样例输出
7
数据规模和约定
对于100%的数据，num <= 100000，高度<=10000。
题目链接：小明爬山
思路：
可以很容易看出是求最长上升子序列的题，根据其思想去解决
求解：
- 方法一：使用动态规划的思想
a：状态的表示： d p [ i ] dp[i] dp[i] 表示以第 i 个数结尾的最长上升子序列的长度
b：状态转移：如果第 i 个数大于以第1~ i-1的某个数结尾的数 j，那么 d p [ i ] dp[i] dp[i] 就可以由 d p [ j ] dp[j] dp[j]得到，值为 d p [ j ] + 1 dp[j]+1 dp[j]+1
代码：
import java.util.Scanner;
public class Main {
static int[] nums = new int[1000001];
static int[] dp = new int[1000001];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int i = 1; i <= n; i++)
nums[i] = sc.nextInt();
dp[1] = 1; //初始化
int max = 1; //最长长度
for (int i = 2; i <= n; i++) {
dp[i] = 1; //每一位数都可以由自身构成长度为1的子序列
for (int j = 1; j < i; j++) {//更新长度
if(nums[i] > nums[j])
dp[i] = Math.max(dp[i], dp[j] + 1);
}
max = Math.max(max, dp[i]);
}
System.out.println(max);
}
}
复杂度分析：
两个for循环会达到
O
(
n
2
)
O(n^2)
O(n2)，数据量大会超时，所以只能通过部分测试点。
- 方法二：利用序列自身特征去巧算，此方法需要一个辅助数组统计最长上升子序列的长度。
a：数组 tmp[]临时存储山的高度，len统计tmp[]内的数据个数，high[]为原始序列。
b：初始化： t m p [ 1 ] = h i g h [ 1 ] ， l e n = 1 tmp[1] = high[1]， len = 1 tmp[1]=high[1]，len=1
c：操作步骤：逐个处理high[]中的数字：当处理 h i g h [ k ] high[k] high[k] 时：
① h i g h [ k ] high[k] high[k] 比 t m p [ l e n ] tmp[len] tmp[len] 大，就将其加到tmp[]末尾，len + 1。
② h i g h [ k ] high[k] high[k] 比 t m p [ l e n ] tmp[len] tmp[len] 小，替换tmp[]中第一个大于等于它的数字
下面举个例
high[ ] = {4，8，9，5，6，7}
这里说明一下为什么要替换第一个大于等于它的数字 ？
因为后面可能有很多数都比
t
m
p
[
l
e
n
]
tmp[len]
tmp[len] 小，而用这些数组成子序列可能会有更好的结果，我们用比
t
m
p
[
l
e
n
]
tmp[len]
tmp[len] 小的
h
i
g
h
[
i
]
high[i]
high[i] 替换第一个大于等于它的数既并不会影响
l
e
n
len
len 的最终长度，也保证了后面小于
t
m
p
[
l
e
n
]
tmp[len]
tmp[len] 的数也能去尝试构成结果序列的一部分。
就像上面表格的第三行
4
，
8
，
9
4，8，9
4，8，9 来说，若小于 9 的 5 不替换大于等于它的第一个数，就得不到最终的结果序列
4
，
5
，
6
，
7
4，5，6，7
4，5，6，7。
代码：
import java.util.Scanner;
public class Main {
static int[] high = new int[100001]; //存放山高度的数组
static int[] tmp = new int[100001]; //辅助统计最长递增子序列的数组
static int n; //山的数量
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 1; i <= n; i++)
high[i] = sc.nextInt();
System.out.println(getLIS());
}
public static int getLIS() { //获取最长长度
int len = 1;
tmp[1] = high[1]; //初始化
for (int i = 2; i <= n; i++) {
if(high[i] > tmp[len]) //符合递增条件，直接放入
tmp[++len] = high[i];
else { //不是递增的就替换第一个不小于它的数
int j = findIndex(i, len); //查找第一个不小于它的数
tmp[j] = high[i]; //替换
}
}
return len;
}
public static int findIndex(int k, int len) {//利用二分查找，降低复杂度
int l = 1, r = len;
int num = high[k], res = r;
while(l < r) {
int mid = (l + r) >> 1;
if(tmp[mid] >= num) {//大于或等于就改变res和右区间
res = mid;
r = mid;
}
else //小于就改变左区间
l = mid + 1;
}
return res;
}
}
复杂度分析：for循环中二分，复杂度为
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)。成功AC。
