公司一个实习生出去秋招，碰到了这样一道题
这道题看起来什么密码的挺复杂，仔细一读题 原来是求一个序列的严格最长上升子序列
这里有两个问题
-什么是子序列
-什么是严格上升
1.子序列就是说... 这里就不用数学语言描述了 ，举个例子
(1, 7, 3, 5, 9, 4, 8)对于这个序列的子序列有(1, 7, 9), (3, 4, 8), (1, 3, 5, 8)等等。也就是说可以不连续，但是先后顺序不能乱。
2.严格上升就是输不能有相等,比如（1,2,2）
上述问题就是求在这些个严格上升的子序列中，找出一个长度最长的子序列，输出的是长度（注意，没有要求找出具体的子序列是什么，只要长度）
明白了题意，我们开始分析
一般最长，最多，最大等最优问题，可以优先考虑动态规划，动态规划的一个特点就是当前解可以由上一个阶段的解推出， 由此，把我们要求的问题简化成一个更小的子问题。子问题具有相同的求解方式，只不过是规模小了而已。最长上升子序列就符合这一特性。我们要求n个数的最长上升子序列，可以求前n-1个数的最长上升子序列，再跟第n个数进行判断。求前n-1个数的最长上升子序列，可以通过求前n-2个数的最长上升子序列……直到求前1个数的最长上升子序列，此时LIS（Longest Increasing Subsequence）当然为1。
让我们举个例子：求 2 7 1 5 6 4 3 8 9 的最长上升子序列。我们定义dp[i] (i∈[1,n])来表示前i个数以array[i]结尾的最长上升子序列长度。
那么
dp[1]=1 子序列为2；
- 考虑前两个元素(dp[2]):
由于7>2 那么（2,7）构成一个上升子序列
dp[2] = dp[1]+1 - 考虑前三个元素(dp[3])：
第三个元素为1，没有比1 小的元素了，于是序列（2,7,1），以1结尾的最长上升子序列 只能是 （1） 即dp[3] = 1 - 考虑前四个元素(dp[4])：
第四个元素为5 ，在5 之前，比5 小的元素有2,1
也就是说可能的上升序列为[2,5],[1,5]
dp[4] = max(dp[1]+1,dp[3]+1) -> dp[4] =2 - 考虑前五个元素（dp[5]）
第五个元素为 6 ，在6之前 ，比6小的有2,1,5
那么dp[6] = max(dp[1]+1,dp[3]+1,dp[4]+1) ->dp[6] = 3
.....
....
考虑前9个元素，也就是整个序列
dp[9] = max(dp[1]+1,dp[2]+1,dp[3]+1,dp[4]+1,dp[5]+1....dp[8]+1)
这里再强调一下dp[9] 是以9 结尾的最长上升子序列的长度
上面我们考虑了dp[1], dp[2],dp[3]......dp[9]
也就是说我们现在知道了以每个元素结尾的最长上升子序列的长度后，最长的那个就是 本题答案
res = max(dp[i]) (i∈[1,n])
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| array[i] | 2 | 7 | 1 | 5 | 6 | 4 | 3 | 8 | 9 |
| dp[i] | 1 | 2 | 1 | 2 | 3 | 2 | 2 | 4 | 5 |
分析到这里其实代码已经可以写出来了，如果写不出来，那么就请看下面的Code
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int res = -1;
Arrays.fill(dp, 1);
if ( nums.length < 1) {
return nums.length;
}
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {//向前找看看有哪个元素比nums[i]小
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
if (dp[i] > res) {
res = dp[i];
}
}
return res;
}
如果我们用上面的代码进行提交，那么这道题的三十分是拿不到的，为什么呢，首先确定一下，上面的代码正确性来讲肯定是没有问题，那么问题出在哪里呢
我们继续来看题，
第一行 时间限制 1000ms ,也就是在1s内解决，我们在来看一下数据规模，10^9
回顾一下之前的分享
有兴趣可以看我之前的简书《算法从入门到放弃》
上述代码的时间复杂度为O(n^2),那么需要继续来优化，根据数据规模，我们需要找一个O（nlogn）级别的算法。
解法2（贪心+二分）
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
分析，什么情况下能达到上升子序列最长呢，我们发现一个上升子序列最后一个元素越小，那么它成长为最长的上升子序列的可能就越大 比如说A=(1,3,9）和B =(1,4,6）两个子序列，现在有一个元素为8，显然对于B序列能组成更长的上升子序列（1,4,6,8）而A序列就不行（1,3,9,8）,
- 那么我们就有了这样的想法，维护一个栈，当扫描到的新元素比栈顶的元素还大，那么直接加入栈中，如果新元素比栈顶元素小，那么我们就从栈中找到第一个比他大的元素，替换掉，来增加最长上升子序列的可能。
我们还是用上面的数据进行举例
2 7 1 5 6 4 3 8 9
这里要强调一下，栈里面的元素不是正确的最长上升子序列，只有长度是正确的，正确的一个解应该是 1 5 6 8 9,，那么对比一下栈里的数，发现5变成了3，那么它的最长上升子序列的可能性增加了，比如说，原始数据我在加几个数，变成 ·····4 3 8 9 -4 5 6 7 8 9 那么栈中的元素变成 1 3 4 5 6 7 8 9. 这样3 的可能性就体现出来了。
知道了这个过程，还有一个问题，就是如何找有序数组中第一个第一个比当前元素大的数（lower_bound）,这个过程和在有序数组中用二分查找非常类似，有兴趣的读者可以看看《算法从入门到放弃》,里面详细的分析了二分查找，对于lower_bound，我们只需要稍微的修改一下就可以。
//int[] cc = {1, 2, 5, 5, 6, 9, 12};(cc,5)-> { 2}
public static int lowerBound(int[] arr, int tag) {
int l = 0, r = arr.length;
while (l <= r) {
int mid = (l + r) >> 1;
if (tag <= arr[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
}
//System.out.println(l); 2
return arr[l];
}
有了这个 那么代码基本都可以写出来了，如果写不出来，请看下面：
public int lengthOfLIS2(int[] nums) {
if (nums.length < 1) {
return nums.length;
}
int[] stack = new int[nums.length];
stack[0] = nums[0];
int top = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > stack[top]) {
stack[++top] = nums[i];
} else {
int left = 0, right = top;
while (left <= right) {
int min = left + (right - left) / 2;
if (nums[i] < stack[min]) {
right = min - 1;
} else if (nums[i] > stack[min]) {
left = min + 1;
} else {//=
right = min - 1;
}
}
stack[left] = nums[i];
System.out.println(Arrays.toString(stack));
}
}
System.out.println(Arrays.toString(stack));
return top + 1;
}
对于这道面试题，上述代码只有逻辑是正确的，并不符合题目要求的输入格式，所以真正机试的时候还要考虑输入格式的问题。
