C++에서 주어진 차이의 가장 긴 산술 부분 수열

정수 배열 arr과 정수 차이가 있다고 가정하면 arr에서 가장 긴 부분 시퀀스의 길이를 찾아야 합니다. 차이와 동일합니다. 따라서 입력이 [1,5,7,8,5,3,4,2,1]이고 차이가 -2이면 가장 긴 산술 시퀀스가 ​​[7,5, 3,1]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 지도 정의
• n :=배열의 크기 arr, 설정:=0
• 0 ~ n – 1 범위의 i에 대해
  • x :=arr[i]
  • m[x] :=1 + m[x - d]
  • ans :=최대 및 m[x]
• 반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#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);
}

입력

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

출력

4