C++ में सबसे लंबा अंकगणित अनुक्रम

मान लीजिए कि हमारे पास पूर्णांकों की एक सरणी ए है, हमें ए में सबसे लंबे अंकगणितीय अनुक्रम की लंबाई वापस करनी होगी। जैसा कि आप जानते हैं कि ए का एक क्रम एक सूची ए [i_1], ए [i_2], ..., ए [ है। i_k] 0 के साथ <=i_1

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक नक्शा बनाएं dp, n:=A का आकार, सेट रिट:=2

• मैं के लिए 0 से n - 1 की सीमा में

  • j के लिए 0 से i - 1 की सीमा में

    • अंतर:=ए [जे] - ए [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