lengh of lis

da183 · da183 · commit 1c5defeb6db1 · 2020-07-12T19:28:21.000+08:00
diff --git a/basic_algorithm/dp.md b/basic_algorithm/dp.md
@@ -348,38 +348,65 @@ int minCut(string s) {
 
 > &#32473;&#23450;&#19968;&#20010;&#26080;&#24207;&#30340;&#25972;&#25968;&#25968;&#32452;&#65292;&#25214;&#21040;&#20854;&#20013;&#26368;&#38271;&#19978;&#21319;&#23376;&#24207;&#21015;&#30340;&#38271;&#24230;&#12290;
 
-```go
-func lengthOfLIS(nums []int) int {
-    // f[i] &#34920;&#31034;&#20174;0&#24320;&#22987;&#21040;i&#32467;&#23614;&#30340;&#26368;&#38271;&#24207;&#21015;&#38271;&#24230;
-    // f[i] = max(f[j])+1 ,a[j]<a[i]
-    // f[0...n-1] = 1
-    // max(f[0]...f[n-1])
-    if len(nums) == 0 || len(nums) == 1 {
-        return len(nums)
-    }
-    f := make([]int, len(nums))
-    f[0] = 1
-    for i := 1; i < len(nums); i++ {
-        f[i] = 1
-        for j := 0; j < i; j++ {
-            if nums[j] < nums[i] {
-                f[i] = max(f[i], f[j]+1)
+```c++
+#pragma region &#22797;&#26434;&#24230;O(n^2)
+int lengthOfLIS1(vector<int>& nums) {
+    if (nums.size() < 2) {
+        return nums.size();
+    }
+
+    vector<int> cache(nums.size());
+    cache[0] = 1;
+    for (int i = 1; i < nums.size(); ++i) {
+        cache[i] = 1;
+        for (int j = 0; j < i; ++j) {
+            if (nums[j] < nums[i]) {
+                cache[i] = max(cache[i], cache[j] + 1);
             }
         }
     }
-    result := f[0]
-    for i := 1; i < len(nums); i++ {
-        result = max(result, f[i])
+    auto maxLen = cache[0];
+    for (const auto &item : cache) {
+        maxLen = max(maxLen, item);
     }
-    return result
-
+    return maxLen;
 }
-func max(a, b int) int {
-    if a > b {
-        return a
+#pragma endregion
+
+#pragma region &#22797;&#26434;&#24230;O(n log n)
+// &#39064;&#30446;&#32473;&#20102;&#25552;&#31034;&#65292;&#30475;&#21040;log n&#21487;&#20197;&#32771;&#34385;&#24448;&#20108;&#20998;&#26597;&#25214;&#20043;&#31867;&#30340;&#19978;&#20945;
+int lengthOfLIS(vector<int> &nums) {
+    int size = nums.size();
+    if (size < 2) {
+        return size;
     }
-    return b
+
+    // tail[i]&#34920;&#31034;&#38271;&#24230;&#20026;i + 1&#30340;&#23376;&#24207;&#21015;&#30340;&#26368;&#23567;&#26411;&#23614;&#20540;
+    // tail&#24517;&#23450;&#21333;&#35843;&#36882;&#22686;&#65292;&#21333;&#35843;&#26632;
+    // &#22914;&#26524;&#24403;&#21069;&#33410;&#28857;&#22823;&#20110;&#26632;&#39030;&#65292;&#21363;&#65292;&#27604;&#26368;&#38271;&#23376;&#24207;&#21015;&#30340;&#26411;&#23614;&#36824;&#22823;&#65292;&#20837;&#26632;&#65288;&#38271;&#24230;+1
+    // &#21542;&#21017;&#36890;&#36807;&#20108;&#20998;&#26597;&#25214;&#25214;&#21040;&#31532;&#19968;&#20010;&#27604;&#24403;&#21069;&#33410;&#28857;&#22823;&#30340;&#20540;&#65292;&#36827;&#34892;&#26356;&#26032;&#12290;&#23376;&#24207;&#21015;&#38271;&#24230;&#30456;&#21516;&#65292;&#26411;&#23614;&#33410;&#28857;&#21464;&#23567;
+    vector<int> tail;
+    tail.push_back(nums.front());
+    for (int i = 1; i < size; ++i) {
+        if (nums[i] > tail.back()) {
+            tail.push_back(nums[i]);
+            continue;
+        }
+        auto left = 0;
+        auto right = tail.size() - 1;
+        while (left < right) {
+            int mid = left + (right - left) / 2;
+            if (tail[mid] < nums[i]) {
+                left = mid + 1;
+            } else {
+                right = mid;
+            }
+        }
+        tail[left] = nums[i];
+    }
+    return tail.size();
 }
+#pragma endregion
 ```
 
 ### [word-break](https://leetcode-cn.com/problems/word-break/)
