最大长度子序列,相邻元素之间的差在C ++中为0或1

给我们一个任意大小的数组,任务是找到给定数组中的子序列,其相邻元素之间的差为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。

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

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

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

  • 取一个与输入数组大小相同的临时数组,假设temp [size]和另一个变量max并将其设置为0

  • 从0到数组大小开始循环

  • 在循环内部,将temp [i]设置为1

  • 从1到大小开始另一个循环

  • 在循环内,从0开始另一个循环j,直到j小于i

  • 在循环内部,检查是否相邻元素之间的差为0或1,然后将temp [i]设置为temp [i] + 1

  • 从0到大小的启动循环

  • 在循环内,检查maximum是否小于temp [i],然后设置maximum = temp [i]

  • 最大回报

  • 打印结果

示例

#include <bits/stdc++.h>
using namespace std;
//function to calculate the maximum difference
int maximum_adja(int arr[], int size){
   int temp[size], maximum = 0;
   for (int i=0; i<size; i++){
      temp[i] = 1;
   }
   for (int i=1; i<size; i++){
      for (int j=0; j<i; j++){
         if (abs(arr[i] - arr[j]) <= 1 && temp[i] < temp[j] + 1){
            temp[i] = temp[j] + 1;
         }
      }
   }
   for (int i=0; i<size; i++){
      if (maximum < temp[i]){
         maximum = temp[i];
      }
   }
   return maximum;
}
int main(){
   int arr[] = {1, 5, 3, 7, 8, 9, 2};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum length subsequence with difference between adjacent elements as either 0
   or 1 is: "<<maximum_adja(arr, size);
   return 0;
}

输出结果

Maximum length subsequence with difference between adjacent elements as either 0 or 1 is: 3