이 문제에서는 배열과 정수 k가 제공됩니다. 우리의 임무는 c++에서 최대 요소로 k를 사용하여 겹치지 않는 부분 배열의 길이의 최대 합을 찾는 프로그램을 만드는 것입니다.
문제 설명 - 여기에 배열과 정수 k가 있습니다. 이 배열에서 생성할 수 있는 겹치지 않는 모든 하위 배열을 찾아야 합니다. 그리고 생성된 모든 하위 배열의 길이를 합산합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력 - 배열 ={3, 7, 1, 2, 3, 1, 6, 3, 2, 5} k =3
출력 - 7
설명 - 최대 요소가 3인 비중첩 하위 배열:
{3} : length = 1
{1, 2, 3, 1} : length = 4
{3, 2} : length = 2
Sum of length = 1+4+2 = 7 이 문제를 해결하기 위해 우리는 배열을 순회하고 더 작은 모든 요소를 찾고 길이를 유지합니다. 하위 배열(요소의 스트림)에 k가 있으면 합에 길이를 더합니다.
예
솔루션의 작동을 설명하는 프로그램,
#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;
} 출력
The max sum of lengths of non-overlapping subarrays with 3 as max element is 7