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.