Tổng độ dài tối đa của các mảng con không chồng chéo với k là phần tử tối đa trong C ++

Trong bài toán này, chúng ta cho một mảng và một số nguyên k. Nhiệm vụ của chúng tôi là tạo một chương trình sẽ tìm tổng độ dài tối đa của các mảng con không chồng chéo với k là phần tử tối đa trong c ++.

Mô tả sự cố - ở đây, chúng ta có một mảng và một số nguyên k. Chúng ta phải tìm tất cả các mảng con không chồng chéo có thể được tạo ra từ mảng này. Và tính tổng độ dài của tất cả các mảng con đã tạo.

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

Đầu vào - mảng ={3, 7, 1, 2, 3, 1, 6, 3, 2, 5} k =3

Đầu ra - 7

Giải thích - các mảng con không chồng chéo với phần tử tối đa 3:

{3} : length = 1
{1, 2, 3, 1} : length = 4
{3, 2} : length = 2
Sum of length = 1+4+2 = 7

Để giải quyết vấn đề này, chúng ta sẽ duyệt qua mảng và tìm tất cả các phần tử nhỏ hơn và duy trì độ dài, nếu mảng con (dòng các phần tử) có k thì hãy cộng độ dài thành tổng.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

#include <iostream>
using namespace std;
int subArrayLengthSum(int arr[], int n, int k){
   int lengthSum = 0;
   int subarrayLength = 0;
   int flag = 0;
   for (int i = 0; i < n;) {
      subarrayLength = 0;
      flag = 0;
      while (arr[i] <= k && i < n) {
         subarrayLength++;
         if (arr[i] == k)
            flag = 1;
         i++;
      }
      if (flag == 1)
      lengthSum += subarrayLength;
      while (arr[i] > k && i < n)
      i++;
   }
   return lengthSum;
}
int main(){
   int arr[] = {3, 7, 1, 2, 3, 1, 6, 3, 2, 5};
   int size = sizeof(arr) / sizeof(arr[0]);
   int k = 3;
   int ans = subArrayLengthSum(arr, size, k);
   cout<<"The max sum of lengths of non-overlapping subarrays with "<<k<<" as max element is "<<ans;
   return 0;
}

Đầu ra

The max sum of lengths of non-overlapping subarrays with 3 as max element is 7