 # LeetCode Akuna OA Solution

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 + a + ... + 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<>();
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        }
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 < i-k:
9            q.popleft()
10        ans = max(ans, prefixSum - q)
11        # Ensure monotonicity of the deque before appending (prefixSum, i)
12        while len(q) and q[-1] >= prefixSum:
13            q.pop()
14        q.append((prefixSum, i))
15    return ans