이 문제에서 n개의 양의 정수와 정수 k로 구성된 배열 arr[]가 주어집니다. 우리의 임무는 해당 크기의 모든 하위 배열이 k보다 작은 합계를 갖도록 최대 하위 배열 크기를 찾는 프로그램을 만드는 것입니다.
문제 설명 − 우리는 배열의 요소로부터 크기로 생성된 모든 하위 배열이 k보다 작거나 같은 요소의 합을 갖도록 하위 배열의 가장 큰 크기를 찾아야 합니다.
문제를 이해하기 위해 예를 들어 보겠습니다.
입력
arr[n] = {4, 1, 3, 2}, k = 9 출력
3
설명
크기가 3인 모든 하위 배열과 그 합 -
{4, 1, 3} = 8
{1, 3, 2} = 6
The sum of all subarrays of size 3 is less than or equal to k. 솔루션 접근 방식
문제에 대한 간단한 해결책은 k보다 큰 크기를 가질 수 있는 부분배열을 찾는 것입니다. 이를 위해 주어진 인덱스까지 요소의 합을 나타내는 접두사 sum을 생성합니다. 이 접두사 합계의 경우 k보다 작은 최대 결과를 찾고 이것의 색인이 결과가 됩니다. 여기에서 접두사 합계가 모든 크기에 대해 k보다 크고 나머지는 모두 합계가 있는 경우라는 사실을 사용했습니다. 이보다 작으면 길이가 -1인 모든 하위 배열의 합은 k보다 작습니다.
예시
우리 솔루션의 작동을 설명하는 프로그램
#include<iostream>
using namespace std;
int calcSubArraySize(int arr[], int n, int k){
int prefixSum[n + 1];
prefixSum[0] = 0;
for (int i = 0; i < n; i++)
prefixSum[i + 1] = prefixSum[i] + arr[i];
// Searching size
int maxLen = −1;
int start = 1, end = n;
int mid, i;
while (start <= end){
int mid = (start + end) / 2;
for (i = mid; i <= n; i++){
if (prefixSum[i] − prefixSum[i − mid] > k)
break;
}
if (i == n + 1){
start = mid + 1;
maxLen = mid;
}
else
end = mid − 1;
}
return maxLen;
}
int main(){
int arr[] = {4, 1, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 9;
cout<<"The maximum subarray size, such that all subarrays of that
size have sum less than k is "<<calcSubArraySize(arr, n, k);
return 0;
} 출력
이 방법은 효율적이지만 문제를 해결하기 위해 더 나은 접근 방식을 만들 수 있습니다.
이 접근 방식에서는 하위 배열의 합을 찾기 위해 슬라이딩 창 방법을 사용합니다. 모든 요소를 취하는 것으로 시작하여 합이 k보다 높게 유지될 때까지의 길이를 찾을 것입니다. 그런 다음 모든 하위 배열의 합이 0보다 작거나 같은 하위 배열의 최대 크기인 length - 1을 반환합니다.
예시
우리 솔루션의 작동을 설명하는 프로그램
#include <iostream>
using namespace std;
int calcSubArraySizeSW(int arr[], int n, int k){
int maxLen = n;
int subArraySum = 0;
int start = 0;
for (int end = 0; end < n; end++){
subArraySum += arr[end];
while (subArraySum > k) {
subArraySum −= arr[start];
start++;
maxLen = min(maxLen, end − start + 1);
if (subArraySum == 0)
break;
}
if (subArraySum == 0) {
maxLen = −1;
break;
}
}
return maxLen;
}
int main(){
int arr[] = { 4, 1, 3, 2, 6 };
int k = 12;
int n = sizeof(arr)/ sizeof(arr[0]);
cout<<"The maximum subarray size, such that all subarrays of that
size have sum less than k is "<<calcSubArraySizeSW(arr, n, k);
return 0;
} 출력
The maximum subarray size, such that all subarrays of that size have sum less than k is 4