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]と別の変数の最大値を使用して、0に設定します。
• 0から配列のサイズまでのループを開始します
• ループ内で、temp[i]を1に設定します
• 1からサイズまで別のループを開始します
• ループ内で、0からjがi未満になるまで別のループjを開始します
• ループ内で、差が0または1の隣接する要素かどうかを確認してから、temp [i]+1でtemp[i]を設定します
• 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