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로 시작하고 끝납니다.

이 문제를 해결하기 위해 배열에서 첫 번째와 마지막 항목을 찾은 다음 공식을 사용하여 −

하위 배열 길이 =lastOccurrence - firstOccurrence + 1

모든 결과의 최대 길이를 찾습니다.

해법을 이해하기 위해 예를 들어 보겠습니다.

배열 ={a, b, a, c, b, a}

요소 a, 인덱스 0에서 첫 번째 발생, 인덱스 5에서 마지막 발생

하위 배열 길이 =5 - 0 + 1=4

최대 길이 =6

요소 b , 인덱스 1에서 처음 발생, 인덱스 4에서 마지막 발생

하위 배열 길이 =4 - 1 + 1 =4

최대 길이 =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