Author: Vishal
Tester: Vishal
Editorialist: Vishal
DIFFICULTY:
Easy
PREREQUISITES:
Two Pointers, Sliding Window
PROBLEM:
Given an array representing the prices of sweets and some money M, find the longest contiguous subarray of sweets you can buy.
EXPLANATION:
For each index L, we need to find the largest index R such that A_L + A_L+1 + … + A_R \leq M.
Assume R has already been computed for some L. Changing L to L+1 decreases the sum on the segment [L,R] as A_i > 0 for all i in the range [0,N-1]. Hence, the new R' for L+1 has to be \geq R.
Hence, since we have proved that R is non-decreasing as L increases, we can use the sliding window technique to calculate the longest valid subarray from each index. The final answer would be max(R-L+1), \forall L \in [0,N-1].
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int tt = 1;
cin >> tt;
while (tt--)
{
ll n, m;
cin >> n >> m;
ll a[n];
for (int i = 0; i < n; ++i)
cin >> a[I];
// Cur holds the sum in the range [L,R].
ll ans = 0, r = -1, cur = 0;
for (ll l = 0; l < n; ++l)
{
// Extend 'R', as long as [L,R] valid.
while (r < n - 1 && cur + a[r + 1] <= m)
{
cur += a[r + 1];
r++;
}
// Try to maximize answer using R-L+1.
ans = max(ans, r - l + 1);
// Reduce cur.
cur -= a[l];
}
cout << ans << "\n";
}
}