最长上升子序列问题（LIS）

给定n个整数A1,A2….An,按从左到右的顺序选出尽量多的整数，组成一个上升子序列（子序列可以理解为：删除0或多个数，其他树的顺序不变）。

例如： 序列1，6，2，3，7，5，可以选出1，2，3，5，也可以选出1，6，7，但是前者更长。 选出的上升子序列中相邻元素不能相等。

关于求LIS有两种常用的算法： 暴力找a[j] O（n2） 用二分来找a[j] O（nlogn）

视频图解 最长上升子序列

• 视频图解 最长上升子序列
• 动态规划表格
• 力扣官方分析
  

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }
}

public class Test7 {

  public static void main(String[] args) {
    int[] a = {0, 1, 6, 2, 3, 7, 5};
    maxIncreaseList(a);
    int[] b = {0, 10, 9, 2, 5, 3, 7, 101, 18};
    maxIncreaseList(b);
  }

  private static void maxIncreaseList(int[] a) {
    int[] dp = new int[a.length];
    dp[1] = 1;
    // dp[i] = max{dp[j] + 1}      0 <= j< i
    for (int i = 2; i <= a.length - 1; i++) {
      dp[i] = 1;
      for (int j = 1; j < i; j++) {
        if (a[i] > a[j]) {
          dp[i] = Math.max(dp[j] + 1, dp[i]);
        }
      }
    }
    int max = 1;
    for (int i = 1; i <= a.length - 1; i++) {
      if (dp[i] > max) {
        max = dp[i];
      }
    }
    System.out.println(max);
  }
}

最长不下降子序列

• https://www.pianshen.com/article/6551264924/
• https://www.cnblogs.com/itlqs/p/5743114.html

参考文章

• https://blog.csdn.net/ltrbless/article/details/81318935
• https://blog.csdn.net/weixin_43731933/article/details/96179727
• https://www.cnblogs.com/GodA/p/5180560.html