Grade 12 · Advanced techniques: two pointers, binary search on the answer, monotonic stacksCitește în română

Sliding window: the longest subarray with sum ≤ S

Original: Fereastra glisantă — cea mai lungă secvență cu suma ≤ S

O(n)C++1766 lines3 examples

The idea

All numbers are strictly positive. We keep a window [st, dr] and its sum. We always extend the right end by one element; while the sum exceeds S, we remove elements from the left (st++). Because the values are positive, removing from the left only decreases the sum, so the remaining window is the longest good one ending at dr. Every element enters once and leaves at most once. We print the maximum length and the start position (the first one, if there are several), numbering from 1; if no value is ≤ S, we print 0 0.

Original description (Romanian)

Toate numerele sunt strict pozitive. Ținem o fereastră [st, dr] și suma ei. Extindem mereu capătul drept cu un element; cât timp suma depășește S, scoatem elemente din stânga (st++). Pentru că valorile sunt pozitive, scoaterea din stânga doar scade suma, deci fereastra rămasă este cea mai lungă bună care se termină în dr. Fiecare element intră o dată și iese cel mult o dată. Afișăm lungimea maximă și poziția de început (prima, dacă sunt mai multe), numerotând de la 1; dacă nicio valoare nu este ≤ S, afișăm 0 0.

Complexity
O(n)
Grade
Grade 12 (Clasa a XII-a)

Examples

Example 1

Input

10 15
2 7 3 1 5 4 8 1 1 3

Expected output

4 1
Example 2

Input

6 6
9 1 2 3 10 4

Expected output

3 2
Example 3

Input

2 1
5 7

Expected output

0 0

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

fereastra-glisanta-suma-cel-mult-s.cpp
/*
 * Titlu: Fereastra glisantă — cea mai lungă secvență cu suma ≤ S
 * Clasa: 12
 * Capitol: Tehnici avansate: doi pointeri, căutare binară pe răspuns, stive monotone
 * Descriere: Toate numerele sunt strict pozitive. Ținem o fereastră [st, dr] și
 *            suma ei. Extindem mereu capătul drept cu un element; cât timp suma
 *            depășește S, scoatem elemente din stânga (st++). Pentru că valorile
 *            sunt pozitive, scoaterea din stânga doar scade suma, deci fereastra
 *            rămasă este cea mai lungă bună care se termină în dr. Fiecare element
 *            intră o dată și iese cel mult o dată. Afișăm lungimea maximă și
 *            poziția de început (prima, dacă sunt mai multe), numerotând de la 1;
 *            dacă nicio valoare nu este ≤ S, afișăm 0 0.
 * Complexitate: O(n)
 *
 * Exemplu
 * Intrare:
 * 10 15
 * 2 7 3 1 5 4 8 1 1 3
 * Ieșire: 4 1
 *
 * Exemplu
 * Intrare:
 * 6 6
 * 9 1 2 3 10 4
 * Ieșire: 3 2
 *
 * Exemplu
 * Intrare:
 * 2 1
 * 5 7
 * Ieșire: 0 0
 */
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    long long S;
    cin >> n >> S;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    long long suma = 0;
    int st = 1, lungMax = 0, inceput = 0;
    for (int dr = 1; dr <= n; dr++)
    {
        suma += a[dr];
        while (suma > S)
        {
            suma -= a[st];
            st++;
        }
        // Fereastra [st, dr] poate fi și vidă (st = dr + 1).
        if (dr - st + 1 > lungMax)
        {
            lungMax = dr - st + 1;
            inceput = st;
        }
    }
    cout << lungMax << ' ' << inceput << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.