数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学相邻元素差为 0 或 1 的最大长度子序列 | C++ 中的集合 2
给定一个任意大小的数组，任务是找到该数组中的子序列，其元素相邻元素之间的差为 0 或 1。
输入 − int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6}
输出 − 相邻元素差为 0 或 1 的最大长度子序列是：3
说明 − 数组中相邻元素的子序列，其差值为 0 或 1，为 {2, 1}。因此，子序列的最大长度为 2。
输入 − int arr[] = { 2, 1, 7, 6, 5}
输出 − 相邻元素差为 0 或 1 的最大长度子序列是：3
说明 − 数组中相邻元素的差值为 0 或 1 的子序列为 {7, 6, 5}。因此，子序列的最大长度为 3。
下面程序中使用的方法如下
输入一个整数类型的数组，其中可以包含正数和负数。
计算数组的大小，并将数组和大小传递给函数以进行进一步的功能。
取一个临时变量 maximum 并将其设置为 0，再取另一个临时变量 i 并将其设置为 0。
创建一个 unordered_map 类型的变量 un_map。
启动循环，直到 i 小于 size。
在循环内部，将 len 设置为 0，并检查是否 un_map.find(arr[i]-1) != un_map.end() && len < un_map[arr[i]-1]，如果是，则将 len 设置为 len = un_map[arr[i]-1]。
检查是否 un_map.find(arr[i]) != un_map.end() && len < un_map[arr[i]]，如果是，则将 len 设置为 len = un_map[arr[i]]。
检查是否 un_map.find(arr[i]+1) != un_map.end() && len < un_map[arr[i]+1]，如果是，则将 len 设置为 len = un_map[arr[i]+1]。
现在设置 un_map[arr[i]] = len + 1。
检查 maximum 是否小于 un_map[arr[i]]，如果是，则将 maximum 设置为 un_map[arr[i]]。
递增 i 的值。
返回 maximum。
打印结果。
示例
#include <bits/stdc++.h>
using namespace std;
//calculate the maximum subsequence
int maximum_adj(int arr[], int size){
int maximum = 0, i = 0;
unordered_map<int, int> un_map;
while(i < size){
int len = 0;
if (un_map.find(arr[i]-1) != un_map.end() && len < un_map[arr[i]-1]){
len = un_map[arr[i]-1];
}
if (un_map.find(arr[i]) != un_map.end() && len < un_map[arr[i]]){
len = un_map[arr[i]];
}
if (un_map.find(arr[i]+1) != un_map.end() && len < un_map[arr[i]+1]){
len = un_map[arr[i]+1];
}
un_map[arr[i]] = len + 1;
if (maximum < un_map[arr[i]]){
maximum = un_map[arr[i]];
}
i++;
}
return maximum;
}
int main(){
int arr[] = {2, 3, 1, 7, 5, 6, 7, 8};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum length subsequence with difference between adjacent elements as either 0
or 1 are: "<< maximum_adj(arr, size);
return 0;
}输出
Maximum length subsequence with difference between adjacent elements as either 0 or 1 are: 4
119 次浏览
