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

ปัญหา

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมเพื่อหาขนาดเซิร์บอาร์เรย์สูงสุด โดยที่ทุกเซิร์บอาร์เรย์ขนาดนั้นมีผลรวมน้อยกว่า k

สำหรับนี้ เราจะได้รับอาร์เรย์ขนาด N และจำนวนเต็ม k งานของเราคือหาความยาวของเซิร์บอาร์เรย์โดยที่ทุกเซิร์บอาร์เรย์ขนาดนั้นในอาร์เรย์ที่กำหนดมีผลรวมน้อยกว่าหรือเท่ากับ k

ตัวอย่างโค้ด

#include<bits/stdc++.h> 
using namespace std; 

//finding maximum length subarray 
int bsearch(int prefixsum[], int n, int k) { 
    int ans = -1; 
    //performing binary search 
    int left = 1, right = n; 
    while (left <= right) { 
        int mid = (left + right) / 2; 
        int i; 
        for (i = mid; i <= n; i++) { 
            if (prefixsum[i] - prefixsum[i - mid] > k) 
                break; 
        } 
        if (i == n + 1) { 
            left = mid + 1; 
            ans = mid; 
        } 
        else right = mid - 1; 
    } 
    return ans; 
} 

//returning maximum subarray size 
int maxSize(int arr[], int n, int k) { 
    int prefixsum[n + 1]; 
    memset(prefixsum, 0, sizeof(prefixsum)); 
    for (int i = 0; i < n; i++) 
        prefixsum[i + 1] = prefixsum[i] + arr[i]; 
    return bsearch(prefixsum, n, k); 
} 

int main() { 
    int arr[] = {1, 2, 10, 4}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int k = 14; 
    cout << maxSize(arr, n, k) << endl; 
    return 0; 
}

เอาต์พุต

2