1218 added.

liuyubobobo · liuyubobobo · commit d87edd83103e · 2019-10-06T01:58:06.000-07:00
diff --git a/1218-Longest-Arithmetic-Subsequence-of-Given-Difference/cpp-1218/CMakeLists.txt b/1218-Longest-Arithmetic-Subsequence-of-Given-Difference/cpp-1218/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.15)
+project(B)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(B main2.cpp)
diff --git a/1218-Longest-Arithmetic-Subsequence-of-Given-Difference/cpp-1218/main.cpp b/1218-Longest-Arithmetic-Subsequence-of-Given-Difference/cpp-1218/main.cpp
@@ -0,0 +1,47 @@
+/// Source : https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/
+/// Author : liuyubobobo
+/// Time   : 2019-10-05
+
+#include <iostream>
+#include <vector>
+#include <map>
+
+using namespace std;
+
+
+/// Dynamic Programming
+/// Time Complexity: O(n)
+/// Space Complexity: O(n)
+class Solution {
+public:
+    int longestSubsequence(vector<int>& arr, int difference) {
+
+        map<int, int> pos;
+        vector<int> dp(arr.size(), 1);
+        for(int i = 0; i < arr.size(); i ++){
+            int pre = arr[i] - difference;
+            if(pos.count(pre))
+                dp[i] = max(dp[i], dp[pos[pre]] + 1);
+            pos[arr[i]] = i;
+        }
+        return *max_element(dp.begin(), dp.end());
+    }
+};
+
+
+int main() {
+
+    vector<int> arr1 = {1,2,3,4};
+    cout << Solution().longestSubsequence(arr1, 1) << endl;
+    // 4
+
+    vector<int> arr2 = {1,3,5,7};
+    cout << Solution().longestSubsequence(arr2, 1) << endl;
+    // 1
+
+    vector<int> arr3 = {1,5,7,8,5,3,4,2,1};
+    cout << Solution().longestSubsequence(arr3, -2) << endl;
+    // 4
+
+    return 0;
+}
diff --git a/1218-Longest-Arithmetic-Subsequence-of-Given-Difference/cpp-1218/main2.cpp b/1218-Longest-Arithmetic-Subsequence-of-Given-Difference/cpp-1218/main2.cpp
@@ -0,0 +1,46 @@
+/// Source : https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/
+/// Author : liuyubobobo
+/// Time   : 2019-10-06
+
+#include <iostream>
+#include <vector>
+#include <map>
+
+using namespace std;
+
+
+/// Dynamic Programming
+/// More Concise Logic
+/// Time Complexity: O(n)
+/// Space Complexity: O(n)
+class Solution {
+public:
+    int longestSubsequence(vector<int>& arr, int difference) {
+
+        map<int, int> dp;
+        int res = 1;
+        for(int i = 0; i < arr.size(); i ++){
+            dp[arr[i]] = max(dp[arr[i]], dp[arr[i] - difference] + 1);
+            res = max(res, dp[arr[i]]);
+        }
+        return res;
+    }
+};
+
+
+int main() {
+
+    vector<int> arr1 = {1,2,3,4};
+    cout << Solution().longestSubsequence(arr1, 1) << endl;
+    // 4
+
+    vector<int> arr2 = {1,3,5,7};
+    cout << Solution().longestSubsequence(arr2, 1) << endl;
+    // 1
+
+    vector<int> arr3 = {1,5,7,8,5,3,4,2,1};
+    cout << Solution().longestSubsequence(arr3, -2) << endl;
+    // 4
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -863,4 +863,5 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 1210 | [Minimum Moves to Reach Target with Rotations](https://leetcode.com/problems/minimum-moves-to-reach-target-with-rotations/) | [无] | [C++](1210-Minimum-Moves-to-Reach-Target-with-Rotations/cpp-1210/) | | |
 | | | | | | |
 | 1217 | [Play with Chips](https://leetcode.com/problems/play-with-chips/) | [无] | [C++](1217-Play with Chips/cpp-1217/) | | |
+| 1218 | [Longest Arithmetic Subsequence of Given Difference](https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/) | [无] | [C++](1218-Longest-Arithmetic-Subsequence-of-Given-Difference/cpp-1218/) | | |
 | | | | | | |
