資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究在 C++ 中給定差值最長的等差數列
假設我們有一個整數陣列 arr 和一個整數差值，我們需要找出 arr 中最長子序列的長度，此子序列是一個等差數列，且子序列中相鄰元素之間的差值與差值相同。因此，如果輸入類似於 [1,5,7,8,5,3,4,2,1]，且差值是 -2，則輸出將為 − 4，因為最長的等差數列是 [7,5,3,1]
為了解決這個問題，我們將按照以下步驟進行操作 −
- 定義對映 m
- n := 陣列 arr 的大小，設定 ans := 0
- 對於從 0 到 n – 1 的範圍內的 i
- x := arr[i]
- m[x] := 1 + m[x - d]
- ans := ans 和 m[x] 的最大值
- 返回 ans
示例
讓我們看看以下實現，以便更好地理解 −
#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
更新時間： 2020 年 4 月 30 日
382 次瀏覽
廣告