สมมติว่าเรามีอาร์เรย์ A ของจำนวนเต็ม เราต้องคืนค่าความยาวของลำดับย่อยเลขคณิตที่ยาวที่สุดใน A ดังที่คุณทราบแล้วว่าลำดับย่อยของ A คือรายการ A[i_1], A[i_2], ..., A[ i_k] ด้วย 0 <=i_1
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
สร้างแผนที่ dp, n :=size of A, set ret :=2
สำหรับฉันอยู่ในช่วง 0 ถึง n – 1
สำหรับ j ในช่วง 0 ถึง i – 1
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
