สมมติว่าเรามีอาร์เรย์จำนวนเต็ม arr และผลต่างของจำนวนเต็ม เราต้องหาความยาวของลำดับย่อยที่ยาวที่สุดใน arr ซึ่งเป็นลำดับเลขคณิตเพื่อให้ความแตกต่างระหว่างองค์ประกอบที่อยู่ติดกันในลำดับต่อมา ก็เหมือนกับความแตกต่าง ดังนั้นหากอินพุตเป็นเหมือน [1,5,7,8,5,3,4,2,1] และผลต่างคือ -2 แล้วผลลัพธ์จะเป็น − 4 เนื่องจากลำดับเลขคณิตที่ยาวที่สุดคือ [7,5, 3,1]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดแผนที่ m
- n :=ขนาดของอาร์เรย์ arr ตั้งค่าเป็น :=0
- สำหรับ i ในช่วง 0 ถึง n – 1
- x :=arr[i]
- m[x] :=1 + m[x - d]
- ans :=สูงสุดของและ m[x]
- คืนสินค้า
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestSubsequence(vector<int>& arr, int d) {
int n = arr.size();
map <int,int> m;
int ans = 0;
for(int i =0;i<n;i++){
int x = arr[i];
m[x] = 1 + (m[x-d]);
ans = max(ans,m[x]);
}
return ans;
}
};
main(){
vector<int> v1 = {1,5,7,8,5,3,4,2,1};
Solution ob;
cout <<ob.longestSubsequence(v1, -2);
} อินพุต
[1,5,7,8,5,3,4,2,1] -2
ผลลัพธ์
4
