vivek_ragi

LONGEST_ARITHMETIC_SUBSEQUENCE

Jun 28th, 2021
643
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // [3, 6, 9, 12]
  2.  
  3. // [[:], [3: 1], [6: 1, 3: 2], [9 : 1, 6: 1, 3: 3]]
  4.  
  5.  
  6. class Solution {
  7. public:
  8.     int longestArithSeqLength(vector<int>& arr) {
  9.         int n = arr.size();
  10.        
  11.         vector<unordered_map<int,int>> dp(n); //previous diff counts for every element
  12.         int ans = 0;
  13.         for(int i = 0; i < n ; ++i) {
  14.             // int curr_elem = arr[i];
  15.            
  16.             for(int j = 0; j < i; ++j) {
  17.                 int diff = arr[j] - arr[i];
  18.                 dp[i][diff] = dp[j].count(diff) >= 1 ? dp[j][diff] + 1 : 2;
  19.                 ans = max(ans, dp[i][diff]);
  20.             }
  21.         }
  22.        
  23.         return ans;
  24.     }
  25. };
RAW Paste Data