ขนาดเซิร์ฟอาร์เรย์สูงสุดที่ทุกเซิร์ฟอาร์เรย์ขนาดนั้นมีผลรวมน้อยกว่า k ในโปรแกรม C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ที่ประกอบด้วยจำนวนเต็มบวก n ตัวและจำนวนเต็ม k ภารกิจของเราคือสร้างโปรแกรมเพื่อหาขนาดเซิร์ฟอาร์เรย์สูงสุด ที่ทำให้ทุกเซิร์ฟอาร์เรย์ขนาดนั้นมีผลรวมน้อยกว่า k

คำอธิบายปัญหา

เราต้องหาขนาดที่ใหญ่ที่สุดของเซิร์ฟอาร์เรย์ ที่ทำให้เซิร์ฟอาร์เรย์ทั้งหมดที่สร้างขึ้นขนาดนั้นจากองค์ประกอบของอาร์เรย์จะมีผลรวมขององค์ประกอบน้อยกว่าหรือเท่ากับ k

ตัวอย่าง

อินพุต

arr[n] = {4, 1, 3, 2}, k = 9

เอาต์พุต

3

คำอธิบาย

เซิร์ฟอาร์เรย์ขนาด 3 ทั้งหมดและผลรวมของพวกเขา:

{4, 1, 3} = 8 
{1, 3, 2} = 6 
ผลรวมของเซิร์ฟอาร์เรย์ขนาด 3 ทั้งหมดน้อยกว่าหรือเท่ากับ k

แนวทางแก้ปัญหา

วิธีแก้ที่ง่ายคือการหาเซิร์ฟอาร์เรย์ที่สามารถมีขนาดมากกว่า k สำหรับสิ่งนี้ เราจะสร้างคำนำหน้าผลรวม (prefix sum) ซึ่งแสดงถึงผลรวมขององค์ประกอบจนถึงดัชนีที่กำหนด สำหรับ prefix sum นี้ เราจะหาผลลัพธ์สูงสุดที่น้อยกว่า k และดัชนีของสิ่งนี้จะเป็นผลลัพธ์ของเรา ที่นี่เราใช้ข้อเท็จจริงที่ว่า หาก prefix sum มากกว่า k สำหรับขนาดใดขนาดหนึ่ง และที่เหลือทั้งหมดมีผลรวมน้อยกว่า แล้วเซิร์ฟอาร์เรย์ทั้งหมดขนาด ลบ 1 จะมีผลรวมน้อยกว่า k

ตัวอย่างโค้ด (วิธี Binary Search + Prefix Sum)

โปรแกรมสำหรับแสดงการทำงานของวิธีแก้ปัญหาของเรา

#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]; 
    // ค้นหาขนาด 
    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; 
}

เอาต์พุต

วิธีนี้มีประสิทธิภาพแต่อยู่ แต่อยู่แต่มีวิธีแก้ที่ดีกว่าสำหรับการแก้ปัญหา

ในแนวทางนี้ เราจะใช้วิธี Sliding Window สำหรับการหาผลรวมของเซิร์ฟอาร์เรย์ เริ่มต้นด้วยการหยิบองค์ประกอบทั้งหมด เราจะหาความยาวจนกว่าผลรวมจะเหนือ k แล้วคืนค่าความยาว - 1 ซึ่งเป็นขนาดสูงสุดของเซิร์ฟอาร์เรย์ที่ผลรวมของเซิร์ฟอาร์เรย์ทั้งหมดน้อยกว่าหรือเท่ากับ 0

ตัวอย่างโค้ด (วิธี Sliding Window)

โปรแกรมสำหรับแสดงการทำงานของวิธีแก้ปัญหาของเรา

#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