Akuna OA
Given an array a
of length n
, find the maximum possible sum from a subarray of length at most k
.
Constraints: 1 <= k <= n <= 1000
Example 1:
Input: a = [2, -3, 5, 3, -1, 2], k = 4
Output: 9
Explanation: The maximum sum subarray is [5, 3, -1, 2]
.
Example 2:
Input: a = [2, -3, 5, 3, -1, 2], k = 3
Output: 8
Explanation: The maximum sum subarray is [5, 3]
. We can't take [5, 3, -1, 2]
as we did in example 1 because it would exceed the maximum length.
Solution
Naive Solution
Try all starting left endpoints and for each one, try all the possible right endpoints, adding one more rightward element each time. This takes .
Model Solution
Let psa[i] = a[0] + a[1] + ... + a[i]
. In other words, psa
is a prefix sum array of a
.
Consider the subarray from l
to r
inclusive. a[l] + a[l+1] + ... + a[r-1] + a[r] = psa[r] - psa[l-1]
.
For every possible r
, find the l
that maximizes psa[r] - psa[l-1]
where r+k-1 <= l <= r
(we still need the length of the subarray to be <=k
). This is still unless we optimize the search for l
.
Let's change what l
represents. Instead of l
and r
characterizing an inclusive subarray, we now exclude the left endpoint, so it has a sum of a[l+1] + a[l+2] + ... + a[r-1] + a[r] = psa[r] - psa[l]
. We change this notation to make indexing simplerāwe get rid of the -1
from psa[l-1]
.
We can create a monotonic deque to store (psa[i], i)
pairs in increasing order of psa[i]
. We loop r
from 0
to n-1
. For each r
, we want the index l
(l < r
) with the minimum psa[l]
, which is the one at the front of the deque. But if l < r-k
, our subarray would be too long. To solve this problem, we remove all l
less than r-k
from the deque. Now we can let l
be the first element of the deque and set ans := max(ans, psa[r]-psa[l])
.
The current r
may be a future left endpoint. To consider this, insert (psa[r], r)
into the deque. To ensure that the deque remains monotonically increasing, we repeatedly pop the back element i
from the deque until psa[i] < psa[r]
(review the Monotonic Stack/Deque Intro article if you're confused). Now we increment r
by 1
and repeat until we loop through the entire array.
Time Complexity
We loop over each element once, insert each element into the deque once, and pop each element from the deque at most once. The time complexity is .
Recall that n <= 1000
, but our solution can work for much larger n
: around the order of 10^8
or 10^9
. This'll sure impress your interviewer. š
Space Complexity
The deque contains up to n
elements. The space complexity is .
C++ Solution
int maxSumSubarray(vector<int> &array, int k) {
int ans = INT_MIN;
deque<pair<int, int>> q;
q.emplace_back(0, -1);
for (int i = 0, prefixSum = 0; i < array.size(); i++) {
prefixSum += array[i];
// Remove left endpoints that are more than distance k away
while (q.size() and q.front().second < i-k) {
q.pop_front();
}
ans = max(ans, prefixSum - q.front().first);
// Ensure monotonicity of the deque before appending (prefixSum, i)
while (q.size() and q.back().first >= prefixSum) {
q.pop_back();
}
q.emplace_back(prefixSum, i);
}
return ans;
}
Java Solution
static class Pair {
int first, second;
Pair(int first, int second) { this.first = first; this.second = second; }
}
static int maxSumSubarray(int[] array, int k) {
int ans = Integer.MIN_VALUE;
Deque<Pair> q = new ArrayDeque<>();
q.addLast(new Pair(0, -1));
for (int i = 0, prefixSum = 0; i < array.length; i++) {
prefixSum += array[i];
// Remove left endpoints that are more than distance k away
while (!q.isEmpty() && q.peekFirst().second < i-k) {
q.removeFirst();
}
ans = Math.max(ans, prefixSum - q.peekFirst().first);
// Ensure monotonicity of the deque before appending (prefixSum, i)
while (!q.isEmpty() && q.peekLast().first >= prefixSum) {
q.removeLast();
}
q.addLast(new Pair(prefixSum, i));
}
return ans;
}
Python Solution
def maxSumSubarray(array, k): ans = -10**9 q = deque([(0, -1)]) prefixSum = 0 for i in range(len(array)): prefixSum += array[i] # Remove left endpoints that are more than distance k away while len(q) and q[0][1] < i-k: q.popleft() ans = max(ans, prefixSum - q[0][0]) # Ensure monotonicity of the deque before appending (prefixSum, i) while len(q) and q[-1][0] >= prefixSum: q.pop() q.append((prefixSum, i)) return ans
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorWhich of the following problems can be solved with backtracking (select multiple)
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!