Mảng con dài nhất có tổng lớn hơn K C++

Cho mảng và số k. Tìm độ dài lớn nhất của mảng con liên tục có tổng > k.

Thuật toán Prefix Sum + Binary Search (O(N log N))

• Tính prefix sum pref[i] = tổng a[0..i].
• Tạo mảng minPrefIdx: chỉ số nhỏ nhất của prefix sum ≤ giá trị đó (sau khi sort).
• Với mỗi i, cần tìm j nhỏ nhất sao cho pref[i] - pref[j] > k ⇔ pref[j] < pref[i] - k.
• Dùng binary search trên mảng prefix sum đã sort.

Triển khai C++

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

int longestSubarraySumGT(int arr[], int n, int k) {
    vector> pref(n);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        pref[i] = {sum, i};
    }
    sort(pref.begin(), pref.end(), [](auto& a, auto& b) {
        return a.first == b.first ? a.second < b.second : a.first < b.first;
    });

    vector minIdx(n);
    minIdx[0] = pref[0].second;
    for (int i = 1; i < n; i++)
        minIdx[i] = min(minIdx[i-1], pref[i].second);

    auto findIdx = [&](int val) {
        int l = 0, r = n-1, ans = -1;
        while (l <= r) {
            int m = (l+r)/2;
            if (pref[m].first <= val) { ans = m; l = m+1; }
            else r = m-1;
        }
        return ans;
    };

    int maxLen = 0;
    sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        if (sum > k) maxLen = i + 1;
        else {
            int idx = findIdx(sum - k - 1);
            if (idx != -1 && minIdx[idx] < i)
                maxLen = max(maxLen, i - minIdx[idx]);
        }
    }
    return maxLen;
}

int main() {
    int arr[] = {5, 3, -3, 2, 4, 7};
    cout << longestSubarraySumGT(arr, 6, 5) << endl; // 6
    return 0;
}

Kết quả

6