aboutsummaryrefslogtreecommitdiff
path: root/other/longest_increasing_subseq.cpp
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
committerJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
commit7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch)
treeeb7a24ee2067f92245c57bb118e85a1baf15df50 /other/longest_increasing_subseq.cpp
parent5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff)
downloadleetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz
leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip
chore: move cpp and rust code to directory
Diffstat (limited to 'other/longest_increasing_subseq.cpp')
-rw-r--r--other/longest_increasing_subseq.cpp48
1 files changed, 48 insertions, 0 deletions
diff --git a/other/longest_increasing_subseq.cpp b/other/longest_increasing_subseq.cpp
new file mode 100644
index 0000000..127a984
--- /dev/null
+++ b/other/longest_increasing_subseq.cpp
@@ -0,0 +1,48 @@
+#include "leetcode.h"
+
+class maxBit {
+public:
+ vector<int> bit;
+ maxBit(int size) { bit.resize(size + 1); }
+ int get(int idx) {
+ int ans = 0;
+ for (; idx > 0; idx -= idx & -idx)
+ ans = max(ans, bit[idx]);
+ return ans;
+ }
+ void update(int idx, int val) {
+ for (; idx < bit.size(); idx += idx & -idx)
+ bit[idx] = max(bit[idx], val);
+ }
+};
+
+class Solution {
+public:
+ int lengthOisLIS(vector<int> &nums) {
+ int uniqueNum = compress(nums);
+ maxBit bit(uniqueNum);
+ for (int x : nums) {
+ int subLongest = bit.get(x - 1);
+ bit.update(x, subLongest + 1);
+ }
+ return bit.get(uniqueNum);
+ }
+
+private:
+ int compress(vector<int> &arr) {
+ vector<int> uniqueSorted(arr);
+ sort(uniqueSorted.begin(), uniqueSorted.end());
+ uniqueSorted.erase(unique(uniqueSorted.begin(), uniqueSorted.end()),
+ uniqueSorted.end());
+ for (int &x : arr)
+ x = lower_bound(uniqueSorted.begin(), uniqueSorted.end(), x) -
+ uniqueSorted.begin() + 1;
+ return uniqueSorted.size();
+ }
+};
+
+int main() {
+ Solution obj;
+ vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
+ cout << obj.lengthOisLIS(nums);
+}