ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ซึ่งประกอบด้วย n จำนวนเต็มบวกและจำนวนเต็ม k งานของเราคือสร้างโปรแกรมเพื่อค้นหาขนาด Maximumsubarray เพื่อให้ subarray ทั้งหมดที่มีขนาดนั้นมีผลรวมน้อยกว่า k
คำอธิบายปัญหา − เราจำเป็นต้องหาขนาดที่ใหญ่ที่สุดของ subarray เพื่อให้ subarray ทั้งหมดที่สร้างขึ้นจากขนาดจากองค์ประกอบของอาร์เรย์จะมีผลรวมขององค์ประกอบที่น้อยกว่าหรือเท่ากับ 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 ได้ สำหรับสิ่งนี้ เราจะสร้างผลรวมคำนำหน้าซึ่งหมายถึงผลรวมขององค์ประกอบจนถึงดัชนีที่กำหนด สำหรับผลรวมคำนำหน้านี้ เราจะพบผลลัพธ์สูงสุดที่น้อยกว่า 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 แล้วคืนค่าความยาว − 1 ซึ่งเป็นขนาดสูงสุดของอาร์เรย์ย่อยที่ผลรวมของอาร์เรย์ย่อยทั้งหมดน้อยกว่าหรือเท่ากับ 0
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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
