Độ dài tối đa của mảng con có phần tử đầu tiên và cuối cùng giống nhau trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng các ký tự. Nhiệm vụ của chúng ta là tạo một chương trình in độ dài tối đa của mảng con có phần tử đầu tiên và cuối cùng giống nhau trong C ++.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào - array ={'t', 'u', 't', 'o', 'r', 'i', 'a', 'l', 's', 'p', 'o', 'i ',' n ',' t '}

Đầu ra - 14

Giải thích -

Mảng con {'t', 'u', 't', 'o', 'r', 'i', 'a', 'l', 's', 'p', 'o', 'i' , 'n', 't'} bắt đầu và kết thúc bằng t.

Để giải quyết vấn đề này, chúng tôi tìm lần xuất hiện đầu tiên và lần xuất hiện cuối cùng của một ký tự trong mảng và sau đó sử dụng công thức -

subarray length =lastOcchood - firstOcchood + 1

Chúng tôi sẽ tìm độ dài tối đa của tất cả các kết quả.

Hãy giải một ví dụ để hiểu giải pháp,

Mảng ={a, b, a, c, b, a}

Yếu tố a, xuất hiện đầu tiên ở chỉ mục 0, xuất hiện cuối cùng ở chỉ mục 5

Độ dài mảng con =5 - 0 + 1 =4

maxLength =6

Yếu tố b, xuất hiện đầu tiên ở chỉ mục 1, xuất hiện cuối cùng ở chỉ mục 4

Độ dài mảng con =4 - 1 + 1 =4

maxLength =6

Ví dụ

Chương trình in độ dài tối đa của mảng con có phần tử đầu tiên và cuối cùng giống nhau -

#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;
}

Đầu ra

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