add q300

yuanguangxin · yuanguangxin · commit 671d379295b6 · 2020-03-16T00:31:03.000+08:00
diff --git a/.idea/workspace.xml b/.idea/workspace.xml
diff --git a/README.md b/README.md
@@ -80,6 +80,7 @@
 * [q5_最长回文子串](/src/动态规划/q5_最长回文子串)
 * [q53_最大子序和](/src/动态规划/q53_最大子序和)
 * [q118_杨辉三角](/src/动态规划/q118_杨辉三角)
+* [q300_最长上升子序列](/src/动态规划/q300_最长上升子序列)
 * [q746_使用最小花费爬楼梯](/src/动态规划/q746_使用最小花费爬楼梯)
 * [q1277_统计全为1的正方形子矩阵](/src/动态规划/q1277_统计全为1的正方形子矩阵)
 
diff --git a/src/动态规划/q300_最长上升子序列/Solution.java b/src/动态规划/q300_最长上升子序列/Solution.java
@@ -0,0 +1,36 @@
+package 动态规划.q300_最长上升子序列;
+
+/**
+ * 动态规划 dp[i]表示以i索引下标结束的最长上升子序列 o(n*log(n))
+ */
+public class Solution {
+
+    public int lengthOfLIS(int[] nums) {
+        if (nums == null || nums.length == 0) {
+            return 0;
+        }
+
+        if (nums.length == 1) {
+            return 1;
+        }
+
+        int n = nums.length;
+        int[] dp = new int[n];
+        int rs = 0;
+
+        for (int i = 0; i < n; i++) {
+            dp[i] = 1;
+            int max = 0;
+            for (int j = i - 1; j >= 0; j--) {
+                if (nums[j] < nums[i] && dp[j] > max) {
+                    max = dp[j];
+                }
+            }
+            dp[i] += max;
+            if (dp[i] > rs) {
+                rs = dp[i];
+            }
+        }
+        return rs;
+    }
+}
