最长等比子序列

#include <iostream>
using namespace std;
#include <vector>
#include <unordered_map>

/* 最长等比子序列 */
int longestArithSeqLength(vector<int>& A) {
    
    if (A.size() == 2) {
    
        return 2;
    }
    if (A.size() == 3) {
    
        return A[2] / A[1] == A[1] / A[0];
    }
    int n = A.size();
    vector<vector<int>> dp(n, vector<int>(n, 2));
    unordered_map<int, vector<int>> cntHashMap;
    for (int i = 0; i < n; ++i) {
    
        cntHashMap[A[i]].emplace_back(i);
    }
    int res = 2;
    for (int i = 1; i < n; ++i) {
    
        for (int j = i + 1; j < n; ++j) {
    
            if (cntHashMap.count(A[i] * A[i] / A[j])) {
    
                for (const auto m : cntHashMap[A[i] * A[i] / A[j]]) {
    
                    if (m < i) {
    
                        dp[i][j] = max(dp[i][j], dp[m][i] + 1);
                    }
                    else {
    
                        break;
                    }
                }
                res = max(res, dp[i][j]);
            }
        }
    }
    return res;
}

int main() {
    

    /*vector<int> A = { 1, 3, 2, 5, 4 };*/

    int N;
    cin >> N;

    vector<int> A(N);

    for (int i = 0; i < N; i++) {
    
        cin >> A[i];
    }

    cout << longestArithSeqLength(A) << endl;

	return 0;

}