C++에서 가장 긴 산술 시퀀스

정수 배열 A가 있다고 가정하면 A에서 가장 긴 산술 부분 수열의 길이를 반환해야 합니다. A의 부분 수열은 목록 A[i_1], A[i_2], ..., A[ i_k] 0 <=i_1

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

• 맵을 dp, n :=A의 크기로 만들고 ret :=2로 설정

• 0 ~ n – 1 범위의 i에 대해

  • 범위 0에서 i – 1의 j에 대해

    • diff :=A[j] – A[i]

    • dp[i, diff] :=1 + dp[j, diff]

    • ret :=최대 1 + dp[i, diff] 및 ret

• 리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int longestArithSeqLength(vector<int>& A) {
      unordered_map <int, unordered_map <int, int> > dp;
      int n = A.size();
      int ret = 2;
      for(int i = 0; i < n; i++){
         for(int j = 0; j < i; j++){
            int diff = A[j] - A[i];
            dp[i][diff] = 1 + dp[j][diff];
            ret = max(1 + dp[i][diff], ret);
         }
      }
      return ret;
   }
};
main(){
   vector<int> v1 = {9,4,7,2,10};
   Solution ob;
   cout << (ob.longestArithSeqLength(v1));
}

입력

[9,4,7,2,10]

출력

3