# PROBLEM LINK:

**Author:** Ankush Khanna

# DIFFICULTY:

Easy

# PREREQUISITES:

Binary Search, Sliding Window Technique

# PROBLEM:

Given a sequence A of N integers find a contiguous sub-sequence with maximum sum not exceeding K. If there are multiple possible such contiguous sub-sequences, find the left most occurrence (starting at the minimum index).

# EXPLANATION:

The problem statement is pretty straightforward for this problem. We need to find a sub-array in A with maximum sum such that it does not exceed K. If there are more than one such sub-arrays, then we have to find the one which has the minimum start index. There are some standard ways to solve this problem. One such way is the sliding window technique which works in O(N) time per test.

In sliding window technique, we use two pointers namely `left`

and `right`

. In each step, we find a window (sub-array) with sum not exceeding K by incrementing `right`

till sum in the range `left`

to `right`

(both inclusive) remains \leq K. Then successively we increment `left`

by 1. And similarly this process goes on until `right`

\leq N.

This strategy works in O(N) time because in the worst case both `left`

and `right`

can be incremented at most N times.

# SOLUTION:

## Setter's Solution

```
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
long k;
cin >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int l = -1, r = -1, l_w = 0, r_w = 0;
long ans = 0L, cur = 0L;
while (r_w < n) {
while (r_w < n && cur + a[r_w] <= k) {
cur += a[r_w];
r_w++;
}
if (cur > ans) {
ans = cur;
l = l_w + 1;
r = r_w;
if (ans == k) {
break;
}
}
cur -= a[l_w];
l_w++;
}
if (!ans) {
cout << "-1\n";
continue;
}
cout << l << ' ' << r << ' ' << ans << '\n';
}
return 0;
}
```

# ALTERNATE SOLUTION:

We can also solve this problem using a binary search implementation using a prefix sum array. It could be done like this:

For each index starting from 1 (1-indexed), find a lower bound of K (binary search) of range sum starting from this index. Just find the maximum range sum not exceeding K this way. It is an O(N\log_{2}{N}) solution which uses O(N) auxiliary space per test.

## Alternate Solution

```
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
long k;
cin >> k;
vector<int> a(n);
vector<long> pre(n + 1);
for (int i = 0; i < n; i++) {
cin >> a[i];
pre[i + 1] = pre[i] + a[i];
}
int l = -1, r = -1;
long ans = 0L;
for (int i = 0; i < n; i++) {
auto it = lower_bound(pre.begin() + i + 1, pre.end(), k + pre[i]);
if (it == pre.end()) {
if (pre.back() - pre[i] > ans) {
ans = pre.back() - pre[i];
l = i + 1;
r = n;
}
break;
} else {
if (*it - pre[i] == k) {
ans = k;
l = i + 1;
r = it - pre.begin();
break;
} else {
int in = it - pre.begin() - 1;
if (pre[in] - pre[i] > ans) {
l = i + 1;
r = in;
ans = pre[in] - pre[i];
}
}
}
}
if (!ans) {
cout << "-1\n";
continue;
}
cout << l << ' ' << r << ' ' << ans << '\n';
}
return 0;
}
```

# COMPLEXITY:

**Time complexity:** O(N) per test.

**Space Complexity:** O(1) auxiliary space per test.

Feel free to share your approach. If you have any queries, they are always welcome.