Trong bài toán này, chúng ta được đưa ra một mảng arr [] gồm n số nguyên dươ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 để tìm kích thước Maximumsubarray, sao cho tất cả các mảng con có kích thước đó có tổng nhỏ hơn k.
Mô tả sự cố - chúng ta cần tìm kích thước lớn nhất của một mảng con, sao cho tất cả mảng con được tạo có kích thước từ các phần tử của mảng sẽ có tổng các phần tử nhỏ hơn hoặc bằng k.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[n] = {4, 1, 3, 2}, k = 9 Đầu ra
3
Giải thích
Tất cả các mảng con có kích thước 3 và tổng của chúng -
{4, 1, 3} = 8
{1, 3, 2} = 6
The sum of all subarrays of size 3 is less than or equal to k. Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tìm mảng con có thể có kích thước lớn hơn k. Đối với điều này, chúng tôi sẽ tạo một tổng tiền tố biểu thị tổng của các phần tử cho đến chỉ số đã cho. Đối với tổng tiền tố này, chúng tôi sẽ tìm thấy kết quả tối đa nhỏ hơn k và chỉ số của điều này sẽ là kết quả của chúng tôi. Ở đây, chúng tôi đã sử dụng thực tế rằng nếu tổng tiền tố lớn hơn k cho bất kỳ kích thước nhỏ hơn, thì tất cả các mảng con có kích thước chiều dài −1 sẽ có tổng nhỏ hơn k.
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 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;
} Đầu ra
Phương pháp này hiệu quả nhưng có thể thực hiện một cách tiếp cận tốt hơn để giải quyết vấn đề,
Trong cách tiếp cận này, chúng tôi sẽ sử dụng phương pháp Cửa sổ trượt để tìm sumof của mảng con. Bắt đầu bằng cách lấy tất cả các phần tử, chúng ta sẽ tìm thấy độ dài cho đến khi tổng vẫn trên k. Và sau đó trả về độ dài - 1 là kích thước tối đa của mảng con mà tổng của tất cả các mảng con nhỏ hơn bằng 0.
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 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;
} Đầu ra
The maximum subarray size, such that all subarrays of that size have sum less than k is 4