题目

image.png

思路

  • 很自然想到要记录比当前值小的有序个数，所以使用dp[i]来记录表示nums[0]到nums[i-1]中比nums[i]小且有序的个数，如何确保dp[i]记录的是有序的最大值，我们需要遍历j取0到i-1中nums[j]比nums[i]小且dp[j]+1为最大的值。

    代码

    1.   public int lengthOfLIS(int[] nums) {
    2.      int len = nums.length;
    3.      if (len <= 0) return len;
    4.      //dp[i]表示0到i-1比nums[i]小的有序个数
    5.      int[] dp = new int[len];
    6.      int max = 0;
    7.      for (int i = 1; i < len; i++) {
    8.         for (int j = 0; j < i; j++) {
    9.             if (nums[i] > nums[j]) {
    10.               dp[i] = Math.max(dp[j] + 1, dp[i]);
    11.             }
    12.         }
    13.         max = Math.max(max, dp[i]);
    14.      }
    15.      return max + 1;
    16.   }
    最长递增子序列