C++で最初と最後の要素が同じであるサブ配列の最大長

この問題では、文字の配列が与えられます。私たちのタスクは、C++で最初と最後の要素が同じであるサブ配列の最大長を出力するプログラムを作成することです。

問題を理解するために例を見てみましょう

入力 −配列={'t'、'u'、't'、'o'、'r'、'i'、'a'、'l'、's'、'p'、'o'、'i '、' n'、' t'}

出力 − 14

説明 −

サブアレイ{'t'、'u'、't'、'o'、'r'、'i'、'a'、'l'、's'、'p'、'o'、'i' 、'n'、't'}はtで始まりtで終わります。

この問題を解決するために、配列内の最初と最後の文字を見つけて、式-

サブアレイの長さ=lastOccurrence-firstOccurrence+ 1

すべての結果の最大の長さを見つけます。

例を解いて解決策を理解しましょう

配列={a、b、a、c、b、a}

要素a、インデックス0での最初の出現、インデックス5での最後の出現

サブアレイの長さ=5-0+ 1 =4

maxLength =6

要素b、インデックス1での最初の出現、インデックス4での最後の出現

サブアレイの長さ=4-1+ 1 =4

maxLength =6

例

最初と最後の要素が同じサブアレイの最大長を出力するプログラム-

#include <iostream>
using namespace std;
int maxSubArrLength(string arr, int n){
   int firstOccurrence, lastOccurrence = -1;
   int maxlength = 0;
   char ch;
   for (int i = 0; i < n; i++){
      ch = arr[i];
      firstOccurrence = lastOccurrence = i;
      for(int j = i; j<n; j++){
         if(arr[j] == ch)
            lastOccurrence = j;
      }
      maxlength = max(maxlength, (lastOccurrence - firstOccurrence + 1));
   }
   return maxlength;
}
int main(){
   string arr = "tutorialsPoint";
   int n = arr.length();
   cout<<"The maximum length of subarray whose first and last elements are same is "<<maxSubArrLength(arr, n);
   return 0;
}

出力

The maximum length of subarray whose first and last elements are same is 14