Cho mảng A các số nguyên, tìm độ dài của dãy con số học dài nhất trong A. Dãy con là dãy A[i_1], A[i_2], ..., A[i_k] với 0 ≤ i_1 < i_2 < ... < i_k ≤ n-1. Dãy B là số học nếu B[i+1] - B[i] bằng nhau với mọi i. Ví dụ: [9,4,7,2,10] cho kết quả 3 (dãy [4,7,10]).
Giải pháp:
Dùng map dp, n := size của A, ret := 2
Với i từ 0 đến n-1:
Với j từ 0 đến i-1:
diff := A[j] - A[i]
dp[i][diff] := 1 + dp[j][diff]
ret := max(ret, 1 + dp[i][diff])Trả về ret
Độ phức tạp O(n²), dp[i][diff] lưu độ dài dãy số học kết thúc tại i với công sai diff.
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; } }; int 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