Dãy số học dài nhất trong C ++

Giả sử chúng ta có một mảng A gồm các số nguyên, chúng ta phải trả về độ dài của dãy con số học dài nhất trong A. Như bạn biết rằng dãy con A là danh sách A [i_1], A [i_2], ..., A [ i_k] với 0 <=i_1

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

• Tạo bản đồ dp, n:=size của A, đặt ret:=2

• cho tôi trong phạm vi từ 0 đến n - 1

  • cho j trong phạm vi 0 đến i - 1

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

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

    • ret:=max of 1 + dp [i, diff] và ret

• trả lại ret

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

Ví dụ

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

Đầu vào

[9,4,7,2,10]

Đầu ra

3