Add C++ implementation

begeekmyfriend · begeekmyfriend · commit dfecd2a80a72 · 2021-02-03T15:55:26.000+08:00
Signed-off-by: begeekmyfriend &lt;begeekmyfriend@gmail.com&gt;
diff --git a/0300_longest_increasing_subsequence/Makefile b/0300_longest_increasing_subsequence/Makefile
@@ -0,0 +1,2 @@
+all:
+	gcc -O1 -o test lis.c
diff --git a/0300_longest_increasing_subsequence/lis.c b/0300_longest_increasing_subsequence/lis.c
@@ -0,0 +1,41 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+
+static int binary_search(int *nums, int lo, int hi, int target)
+{
+    while (lo + 1 < hi) {
+        int mid = lo + (hi - lo) / 2;
+        if (nums[mid] < target) {
+            lo = mid;
+        } else {
+            hi = mid;
+        }
+    }
+    return hi;
+}
+
+int lengthOfLIS(int* nums, int numsSize){
+    int i, piles = 0;
+    int *tops = malloc(numsSize * sizeof(int));
+    for (i = 0; i < numsSize; i++) {
+        int pos = binary_search(tops, -1, piles, nums[i]);
+        if (pos == piles) {
+            piles++;
+        }
+        tops[pos] = nums[i];
+    }
+    return piles;
+}
+
+int main(int argc, char **argv)
+{
+    int i;
+    int *nums = malloc((argc - 1) * sizeof(int));
+    for (i = 0; i < argc - 1; i++) {
+        nums[i] = atoi(argv[i + 1]);
+    }
+
+    printf("%d\n", lengthOfLIS(nums, argc - 1));
+    return 0;
+}
diff --git a/0300_longest_increasing_subsequence/lis.cc b/0300_longest_increasing_subsequence/lis.cc
@@ -0,0 +1,25 @@
+#include <bits/stdc++.h>
+
+using namespace std;
+
+class Solution {
+public:
+    int lengthOfLIS(vector<int>& nums) {
+        vector<int> dp(nums.size(), 1);
+        for (int i = 0; i < nums.size(); i++) {
+            for (int j = 0; j < i; j++) {
+                if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
+                    dp[i] = dp[j] + 1;
+                }
+            }
+        }
+
+        int res = 0;
+        for (int i : dp) {
+            if (i > res) {
+                res = i;
+            }
+        }
+        return res;
+    }
+};
