动态规划LeetCode300最长上升子序列

在做这道题之前，我们先看一下什么是子序列。

区分子串和子序列：

给定 "pwwkew" ，

子串是pww,wwk等很多个子串是连在一起的

子序列是 pwk,pke等很多个子序列，但是子序列中的字符在字符串中不一定是连在一起的。

题目描述：

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

示例:

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

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n^2) 。
进阶: 你能将算法的时间复杂度降低到 O(n*log n) 吗?

思路：dp[i]代表以第i个元素结尾的最长上升子序列的长度。

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

上面这个算法的时间复杂度为O(n^2)。

待会补充一下O(n*log n) 的解法，这个解法是利用栈和二分查找，大家先思考一下。

欢迎评论，共同进步！！