数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告