已知一个序列 {S, S,…,S}，取出若干数组成新的序列 {S, S,…, S}，其中 i1、i2 … im 保持递增，即新序列中各个数仍然保持原数列中的先后顺序，称新序列为原序列的一个 子序列 。
如果在子序列中，当下标 ix > iy 时，S > S，称子序列为原序列的一个 递增子序列 。

300. Longest Increasing Subsequence (Medium)

题目描述
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
思路
dp[n] = max{ dp[i]+1 | S < S && i < n} 。

  1. class Solution {
  2.     public int lengthOfLIS(int[] nums) {
  3.         int len = nums.length;
  4.         int[] dp = new int[len];
  5.         dp[0] = 1;
  6.         int finalnum = 1;
  7.         for(int i=1; i<len; i++){
  8.             int max = 1;
  9.             for(int j=i-1; j>=0; j--){
  10.                 if(nums[i]>nums[j]){
  11.                     max = Math.max(max,dp[j]+1);
  12.                 }
  13.             }
  14.             dp[i] = max;
  15.             if(max>finalnum){
  16.                 finalnum = max;
  17.             }
  18.         }
  19.         return finalnum;
  20.     }
  21. }

优化

以上解法的时间复杂度为 O(N)，可以使用 二分查找 将时间复杂度降低为 O(NlogN)。
考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。
基于上面的贪心思路，我们维护一个数组 d[i] ，表示长度为 i 的最长上升子序列的末尾元素的最小值，用 len 记录目前最长上升子序列的长度，起始时 len 为 1，d[1]=nums[0]。

  1. class Solution {
  2.     public int lengthOfLIS(int[] nums) {
  3.         int len = nums.length;
  4.         int dp[] = new int[len+1];
  5.         dp[0] = 0;
  6.         dp[1] = nums[0];
  7.         int count = 1;
  8.         for(int i=1; i<len; i++){
  9.             if(nums[i]>dp[count]){
  10.                 dp[++count] = nums[i];
  11.             }else{
  12.                 int l = 1, r = count, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
  13.                 while (l <= r) {
  14.                     int mid = (l + r) >> 1;
  15.                     if (dp[mid] < nums[i]) {
  16.                         pos = mid;
  17.                         l = mid + 1;
  18.                     } else {
  19.                         r = mid - 1;
  20.                     }
  21.                 }
  22.                 dp[pos + 1] = nums[i];
  23.             }
  24.         }
  25.         return count;
  26.     }
  27. }

646. Maximum Length of Pair Chain (Medium)

题目描述
给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例
输入：[[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4]
思路
将二维数组按第2列升序排序。排序后的思路同上题。

  1. class Solution {
  2.     public int findLongestChain(int[][] pairs) {
  3.         Arrays.sort(pairs, new Comparator<int[]>(){
  4.             public int compare(int[] p1, int[] p2){
  5.                 if(p1[1]>p2[1]){
  6.                     return -1;
  7.                 }else if(p1[1]==p2[1]){
  8.                     return 0;
  9.                 }else{
  10.                     return 1;
  11.                 }
  12.             }
  13.         });
  14.         int len = pairs.length;
  15.         int[] dp = new int[len];
  16.         dp[0] = 1;
  17.         for(int i=1; i<len; i++){
  18.             int max = 1;
  19.             for(int j=i-1; j>=0; j--){
  20.                 if(pairs[i][1]<pairs[j][0]){
  21.                     max = Math.max(max, dp[j]+1);
  22.                 }
  23.             }
  24.             dp[i] = max;
  25.         }
  26.         return dp[len-1];
  27.     }
  28. }

第一种优化解法

同上题，利用 二分查找 将动态规划的O(n^2)时间复杂度降低为 O(NlogN)。

第二种优化解法

按照数对第二个数的升序序列遍历所有数对，使用贪心思想扩展数对链，在所有可作为下一个数对的集合中选择第二个数最小的数对添加到数对链。

  1. class Solution {
  2.     public int findLongestChain(int[][] pairs) {
  3.         Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
  4.         int cur = Integer.MIN_VALUE, ans = 0;
  5.         for (int[] pair: pairs) if (cur < pair[0]) {
  6.             cur = pair[1];
  7.             ans++;
  8.         }
  9.         return ans;
  10.     }
  11. }

376. Wiggle Subsequence (Medium)

题目描述
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例
输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
思路
我的题解：偏向贪心，将连续数组删除。

  1. class Solution {
  2.     public int wiggleMaxLength(int[] nums) {
  3.         if(nums==null||nums.length==0){
  4.             return 0;
  5.         }
  6.         int len = nums.length;
  7.         int j=0;
  8.         while(j<len-1 && nums[j+1]==nums[j]){
  9.             j++;
  10.         }
  11.         if(j==len-1){
  12.             return 1;
  13.         }
  14.         int count = 2;
  15.         int start = 0;
  17.         for(int i=1; i<len-1; i++){
  18.             if((nums[i+1]-nums[i])*(nums[i]-nums[start])>=0){
  19.                 continue;
  20.             }else{
  21.                 start=i;
  22.                 count++;
  23.             }
  24.         }
  25.         return count;
  26.     }
  27. }

结果
image.png

动态规划解法

思路
up数组维护最后一位上升的最长子序列长度，down数组维护最后一位下降的最长子序列长度。
image.png

  1. class Solution {
  2.     public int wiggleMaxLength(int[] nums) {
  3.         if(nums==null||nums.length==0){
  4.             return 0;
  5.         }
  6.         int len = nums.length;
  7.         int[] up = new int[len];
  8.         int[] down = new int[len];
  9.         up[0] = 1;
  10.         down[0] = 1;
  11.         for(int i=1; i<len; i++){
  12.             if(nums[i]>nums[i-1]){
  13.                 down[i] = down[i-1];
  14.                 up[i] = Math.max(up[i-1], down[i-1]+1);
  15.             }else if(nums[i]<nums[i-1]){
  16.                 up[i] = up[i-1];
  17.                 down[i] = Math.max(down[i-1],up[i-1]+1);
  18.             }else{
  19.                 down[i] = down[i-1];
  20.                 up[i] = up[i-1];
  21.             }
  22.         }
  23.         return Math.max(down[len-1],up[len-1]);
  24.     }
  25. }

优化的动态规划解法

思路
由于每次比较只遇到前一个up或down，将数组缩为单个int。

  1. class Solution {
  2.     public int wiggleMaxLength(int[] nums) {
  3.         if(nums==null||nums.length==0){
  4.             return 0;
  5.         }
  6.         int len = nums.length;
  7.         int up = 1;
  8.         int down = 1;
  9.         for(int i=1; i<len; i++){
  10.             if(nums[i]>nums[i-1]){
  11.                 up = Math.max(up, down+1);
  12.             }else if(nums[i]<nums[i-1]){
  13.                 down = Math.max(down,up+1);
  14.             }
  15.         }
  16.         return Math.max(down,up);
  17.     }
  18. }