Tìm kích thước mảng con lớn nhất sao cho mọi mảng con kích thước đó đều có tổng nhỏ hơn k trong C++

Trong bài toán này, chúng ta được cung cấp một mảng arr[] gồm n số nguyên dương và một số nguyên k. Nhiệm vụ là viết chương trình tìm Kích thước mảng con lớn nhất, sao cho tất cả các mảng con có kích thước đó đều có tổng nhỏ hơn k.

Mô tả bài toán

Ta cần tìm kích thước lớn nhất của một mảng con, sao cho mọi mảng con được tạo ra 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.

Ví dụ minh họa

Đầu vào

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

Đầu ra

3

Giải thích

Tất cả mảng con kích thước 3 và tổng của chúng:
{4, 1, 3} = 8
{1, 3, 2} = 6
Tổng của tất cả mảng con kích thước 3 đều nhỏ hơn hoặc bằng k.

Phương pháp giải

Cách đơn giản: tìm mảng con có thể có kích thước lớn hơn k. Tạo tiền tố tổng (prefix sum) biểu thị tổng các phần tử đến chỉ số đó. Với tiền tố tổng này, tìm kết quả lớn nhất nhỏ hơn k và chỉ số của nó là kết quả. Sử dụng thực tế: nếu tiền tố tổng lớn hơn k cho bất kỳ kích thước nào, và các phần còn lại có tổng nhỏ hơn, thì tất cả mảng con kích thước trừ 1 sẽ có tổng nhỏ hơn k.

Chương trình minh họa (Cách 1 - Tiền tố tổng + Tìm kiếm nhị phân)

#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];
    
    // Tìm kiếm kích thước
    int maxLen = -1;
    int start = 1, end = n;
    int mid, i;
    
    while (start <= end) {
        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 << "Kích thước mảng con lớn nhất mà mọi mảng con kích thước đó có tổng < k là "
         << calcSubArraySize(arr, n, k);
    return 0;
}

Đầu ra

Phương pháp này hiệu quả nhưng có cách tiếp cận tốt hơn để giải quyết bài toán,

Cách tiếp cận tốt hơn: sử dụng phương pháp cửa sổ trượt (Sliding Window) để tìm tổng mảng con. Bắt đầu bằng cách lấy tất cả các phần tử, tìm độ dài đến khi tổng vượt quá k. Sau đó trả về độ dài - 1 là kích thước lớn nhất của mảng con mà tổng của tất cả các mảng con nhỏ hơn hoặc bằng k.

Chương trình minh họa (Cách 2 - Cửa sổ trượt)

#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 << "Kích thước mảng con lớn nhất mà mọi mảng con kích thước đó có tổng < k là "
         << calcSubArraySizeSW(arr, n, k);
    return 0;
}

Đầu ra

Kích thước mảng con lớn nhất mà mọi mảng con kích thước đó có tổng < k là 4