隣接する要素間の差が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.find（arr [i]）！=un_map.end（）&&len を設定します。

• un_map.find（arr [i] +1）！=un_map.end（）&&len を設定します。

• ここで、un_map [arr [i]] =len + 1

  を設定します。

• 最大値がun_map[arr[i]]未満かどうかを確認してから、un_map [arr [i]]

  で最大値を設定します

• iの値をインクリメントする

• 最大値を返す

• 結果を印刷する

例

#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