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.

Naive Solution

Try all starting left endpoints and for each one, try all the $\mathcal{O}(k)$ possible right endpoints, adding one more rightward element each time. This takes $\mathcal{O}(nk)$.

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 $\mathcal{O}(nk)$ 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 $\mathcal{O}(n)$.

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 $\mathcal{O}(n)$.

C++ Solution

1int maxSumSubarray(vector<int> &array, int k) {
2    int ans = INT_MIN;
3    deque<pair<int, int>> q;
4    q.emplace_back(0, -1);
5    for (int i = 0, prefixSum = 0; i < array.size(); i++) {
6        prefixSum += array[i];
7        // Remove left endpoints that are more than distance k away
8        while (q.size() and q.front().second < i-k) {
9            q.pop_front();
10        }
11        ans = max(ans, prefixSum - q.front().first);
12        // Ensure monotonicity of the deque before appending (prefixSum, i)
13        while (q.size() and q.back().first >= prefixSum) {
14            q.pop_back();
15        }
16        q.emplace_back(prefixSum, i);
17    }
18    return ans;
19}

Java Solution

1static class Pair {
2    int first, second;
3    Pair(int first, int second) { this.first = first; this.second = second; }
4}
5
6static int maxSumSubarray(int[] array, int k) {
7    int ans = Integer.MIN_VALUE;
8    Deque<Pair> q = new ArrayDeque<>();
9    q.addLast(new Pair(0, -1));
10    for (int i = 0, prefixSum = 0; i < array.length; i++) {
11        prefixSum += array[i];
12        // Remove left endpoints that are more than distance k away
13        while (!q.isEmpty() && q.peekFirst().second < i-k) {
14            q.removeFirst();
15        }
16        ans = Math.max(ans, prefixSum - q.peekFirst().first);
17        // Ensure monotonicity of the deque before appending (prefixSum, i)
18        while (!q.isEmpty() && q.peekLast().first >= prefixSum) {
19            q.removeLast();
20        }
21        q.addLast(new Pair(prefixSum, i));
22    }
23    return ans;
24}

Python Solution

1def maxSumSubarray(array, k):
2    ans = -10**9
3    q = deque([(0, -1)])
4    prefixSum = 0
5    for i in range(len(array)):
6        prefixSum += array[i]
7        # Remove left endpoints that are more than distance k away
8        while len(q) and q[0][1] < i-k:
9            q.popleft()
10        ans = max(ans, prefixSum - q[0][0])
11        # Ensure monotonicity of the deque before appending (prefixSum, i)
12        while len(q) and q[-1][0] >= prefixSum:
13            q.pop()
14        q.append((prefixSum, i))
15    return ans

Solution Implementation