* Author:* Vishal

*Vishal*

**Tester:***Vishal*

**Editorialist:**# 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";
}
}
```