LeetCode 300. Longest Increasing Subsequence

300. Longest Increasing Subsequence（最长上升子序列）

链接

https://leetcode-cn.com/problems/merge-two-binary-trees

题目

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

思路

n2的我是拿动态规划做的，但是nlogn我没什么思路，就没写。
增加一个dp数组，初始值为1，当遍历到第i个数时，比较前方的所有数，若比第i个数小，就可以构成上升子序列，找到最长的那个存储在dp中，最后输出最大值即可。

代码

public int lengthOfLIS(int[] nums) {
  int len = nums.length;
  if (len <= 0) {
    return 0;
  }
  int[] dp = new int[len];
  dp[0] = 1;
  int max = 1;
  for (int i = 0; i < len; 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);
      }
    }
    if (dp[i] > max) {
      max = dp[i];
    }
  }
  return max;
}