最大长度子序列，相邻元素之间的差为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。

以下程序中使用的方法如下

• 输入一个可以包含正负元素的整数类型数组。

• 计算数组的大小，并将数组和大小传递给函数以获取更多功能。

• 取一个最大的临时变量并将其设置为0，并取另一个临时变量i并将其也设置为0

• 创建类型为unordered_map的变量un_map

• 开始循环，直到我小于大小

• 在循环内，将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

• 检查最大值是否小于un_map [arr [i]]，然后使用un_map [arr [i]]设置最大值

• 增加i的值

• 最大回报

• 打印结果

示例

#include <bits/stdc++.h>
using namespace std;
//计算最大子序列
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