public class Longest_Increasing_Subsequence {
/**
* O(N^2)
* DP
* 思路：
* 示例：[1,0,2,4,10,5]
* 找出以上数组的LIS的长度
* 分析:
* 只要求长度，并不要求找出具体的序列
* 问题可以拆分为
* 1. 对于[1]，找出LIS
* 2. 对于[1,0]，找出LIS
* 3. 对于[1,0,2]，找出LIS
* 4. 对于[1,0,2,4]，找出LIS
* ...
* 最后，对于[1,0,2,4,10,5],找出LIS
* 再进一步思考，例如：
* 找出[-1,0,1,0,2,4]的LIS，就要找到在4之前符合条件（都比4小且都为升序）的LIS的长度 => [-1,0,1]是满足情况的(最长，都是升序，都比4小)
* 那么就要有一个数据结构来记录到某一个index上，LIS的长度。因为每一个index上的LIS长度并不是固定为前一个加1，所以每一个都要记录下来 => 数组dp[]
* dp[i]记录的是，在i这个index上，LIS的长度
* 比如：
* index 0 1 2 3 4 5
* dp:[ 1,2,3,1,4,5] //dp数组
* ar:[-1,0,1,0,2,4] //原数组
* dp[1] = 2表示在1这个index上，LIS的长度是2（[-1,0]）
* dp[4] = 4表示在4这个index上，LIS的长度是4（[-1,0,1,2]）
* ----------------------------
* 状态转换方程：
* dp[i] = dp[k] + 1; (dp[k] = max(dp[0], dp[1], ... dp[i-1])) // dp[i] = 在i以前最大的LIS长度加上1
* 以上方程的成立条件：
* nums[k] < nums[i] //保持递增序列的属性
*/
/**
* O(N^2)
*/
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = 1;
for (int i = 1; i < nums.length; i++) {
int beforeMaxLen = dp[i];
// 在0 ~ i之间比较LIS的长度
for(int j = 0; j < i; j++) {
if (nums[j] < nums[i] && dp[j] > beforeMaxLen) { //注意dp[j] > beforeMaxLen，新的长度要大于之前选出来的长度才能更新
beforeMaxLen = dp[j];
}
}
dp[i] = beforeMaxLen + 1;
}
int max = 0;
// 在数组里找出最大的长度即可
for (int i = 0; i < nums.length; i++) {
if (dp[i] > max){
max = dp[i];
}
}
return max;
}
/**
* O(N*logN)
* 思路：
* 满足递增序列，就直接加入list中
* 如果发现有降序出现，找出在原数组中比它大的第一个数的index，然后在list中替换那个数
* 最后返回list的长度
* 原理：
* 因为只求长度，所以没有必要存储确切的sequence
*/
public int lengthOfLIS_2(int[] nums) {
List<Integer> list = new ArrayList<>();
for(int num : nums) {
if(list.isEmpty() || list.get(list.size() - 1) < num) { // 不满足递增序列
list.add(num);
} else {
list.set(findFirstLargeEqual(list, num), num);
}
}
return list.size();
}
private int findFirstLargeEqual(List<Integer> list, int target)
{
int start = 0;
int end = list.size() - 1;
while(start < end) {
int mid = start + (end - start) / 2;
if(list.get(mid) < target) {
start = mid + 1;
}
else {
end = mid;
}
}
return end;
}
/**
* 测试用
*/
public static void main(String[] args) {
Longest_Increasing_Subsequence lis = new Longest_Increasing_Subsequence();
int[] a = {-1,0,1,0,2,4};
System.out.print(lis.lengthOfLIS_2(a));
}
}