leetcode

commit 47acae7b6715ade1a457a2c8c475577bde086911
parent 923420a4665307da7fe969fb53eac828621a2da8
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 23 Jun 2023 16:00:25 +0200

Daily Problem

Diffstat:
A
Problems/1027.cpp
 | 
28
++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 29 insertions(+), 0 deletions(-)
diff --git a/Problems/1027.cpp b/Problems/1027.cpp
@@ -0,0 +1,28 @@
+class Solution {
+public:
+  int longestArithSeqLength(vector<int> &nums) {
+    unordered_map<int, vector<int>> um;
+    int res = 2;
+
+    for (int i = 0; i < nums.size(); i++) um[nums[i]].push_back(i);
+    for (const auto &[num1, vec1] : um) {
+      res = max(res, (int)vec1.size());
+      for (const auto &[num2, vec2] : um) {
+        if (num1 == num2) continue;
+
+        auto it = lower_bound(vec2.begin(), vec2.end(), vec1.front() + 1);
+        if (it == vec2.end()) continue;
+
+        int diff = num2 - num1, crnt = *it, count = 2, next;
+        while (true) {
+          if (!um.count(next = nums[crnt] + diff)) break;
+          auto it = lower_bound(um[next].begin(), um[next].end(), crnt + 1);
+          if (it == um[next].end()) break;
+          crnt = *it, count++;
+        }
+        res = max(res, count);
+      }
+    }
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -406,6 +406,7 @@ for solving problems.
 |  1020  |   Medium   | [Number of Enclaves](Problems/1020.cpp)                                                          |
 |  1022  |    Easy    | [Sum of Root To Leaf Binary Numbers](Problems/1022.cpp)                                          |
 |  1026  |   Medium   | [Maximum Difference Between Node and Ancestor](Problems/1026.cpp)                                |
+|  1027  |   Medium   | [Longest Arithmetic Subsequence](Problems/1027.cpp)                                              |
 |  1035  |   Medium   | [Uncrossed Lines](Problems/1035.cpp)                                                             |
 |  1038  |   Medium   | [Binary Search Tree to Greater Sum Tree](Problems/1038.cpp)                                      |
 |  1042  |   Medium   | [Flower Planting With No Adjacent](Problems/1042.cpp)                                            |