Dãy số học dài nhất của sự khác biệt cho trước trong C ++

Giả sử chúng ta có một mảng số nguyên arr và một hiệu số nguyên, chúng ta phải tìm độ dài của dãy con dài nhất trong arr là dãy số học sao cho sự khác biệt giữa các phần tử liền kề trong dãy con giống như sự khác biệt. Vì vậy, nếu đầu vào giống như [1,5,7,8,5,3,4,2,1] và chênh lệch là -2, thì đầu ra sẽ là - 4, vì dãy số học dài nhất là [7,5, 3,1]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định bản đồ m
• n:=kích thước của mảng arr, đặt ans:=0
• cho tôi trong phạm vi từ 0 đến n - 1
  • x:=arr [i]
  • m [x]:=1 + m [x - d]
  • ans:=max of and m [x]
• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int longestSubsequence(vector<int>& arr, int d) {
      int n = arr.size();
      map <int,int> m;
      int ans = 0;
      for(int i =0;i<n;i++){
         int x = arr[i];
         m[x] = 1 + (m[x-d]);
         ans = max(ans,m[x]);
      }
      return ans;
   }
};
main(){
   vector<int> v1 = {1,5,7,8,5,3,4,2,1};
   Solution ob;
   cout <<ob.longestSubsequence(v1, -2);
}

Đầu vào

[1,5,7,8,5,3,4,2,1]
-2

Đầu ra

4