no message

frank-lam · frank-lam · commit f7ab48d60975 · 2018-08-05T11:11:59.000+08:00
diff --git a/notes/数据结构与算法.md b/notes/数据结构与算法.md
@@ -1021,6 +1021,41 @@ public class Solution2 {
 
 
 
+### 3. 最长上升子序列
+
+给定一个无序的整数数组，找到其中最长上升子序列的长度。
+
+**示例:**
+
+```
+输入: [10,9,2,5,3,7,101,18]
+输出: 4 
+解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
+```
+
+**说明:**
+
+- 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
+- 你算法的时间复杂度应该为 O(*n2*) 。
+
+**进阶:** 你能将算法的时间复杂度降低到 O(*n* log *n*) 吗?
+
+
+
+LIS( i ) 表示以第 i 个数字为结尾的最长上升子序列的长度
+
+LIS( i ) 表示 [0...i] 的范围内，选择数字nums[i]可以获得的最长上升子序列的长度
+
+LIS ( i )  =   max<sub>j<i</sub>( 1 + LIS( j ) if nums[i] > nums[j] )
+
+
+
+
+
+
+
+
+
 动态规划解决01背包问题 - Christal_R - 博客园
 https://www.cnblogs.com/Christal-R/p/Dynamic_programming.html
 
