Maximum Profit with Limited Subarray Length

You are given an integer array pnl representing daily profit and loss values, and an integer k representing the maximum subarray length you can select.

Return the maximum sum of any subarray of pnl whose length is at most k.

Example 1:

Input: pnl = [-3, 4, 3, -2, 2, 5], k = 4
Output: 8

Explanation:
The subarray [3, -2, 2, 5] has length 4 and sum 8, which is the maximum possible.

Example 2:

Input: pnl = [5, -1, 3, -2, 4], k = 3
Output: 7

Explanation:
The subarray [3, -2, 4] has length 3 and sum 5, 
but subarray [5, -1, 3] has length 3 and sum 7, which is better.

Constraints:

1 <= pnl.length <= 10⁵

-10⁴ <= pnl[i] <= 10⁴

1 <= k <= pnl.length

How to approach?

monotonic deque, prefixSum

function maxProfitWithLimitedSubarray(pnl: number[], k: number): number {
    const n = pnl.length;

    const prefixSum: number[] = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + pnl[i];
    }

    const deque: number[] = [];
    let maxProfit = Number.NEGATIVE_INFINITY;

    for (let i = 0; i <= n; i++) {
        if (deque.length > 0 && deque[0] < i - k) {
            deque.shift();
        }

        if (deque.length > 0) {
            const candidate = prefixSum[i] - prefixSum[deque[0]];
            maxProfit = Math.max(maxProfit, candidate);
        }

        while (deque.length > 0 && prefixSum[deque[deque.length - 1]] >= prefixSum[i]) {
            deque.pop();
        }

        deque.push(i);
    }

    return maxProfit;
}

1. set n as pnl's length.
2. create prefixSum which has length of n+1
3. create for loop to fill the prefixSum array using pnl[i] value. the prefixSum[0] will be 0.
4. create deque to save the indices of prefixSum.
5. set maxProfit as the smallest number in js.
6. create for loop using index increment by one untill n.
7. when deque has length and deque's 0 index value is out of window(smaller than i-k) then it's removing using shift() method. since the subarray length exceeds k length.
8. when deque's length is bigger than 0, then set the candidate using prefixSum's i index value and subtract the prefixSum's deque[0]'s index value.
9. choose which one is bigger using Math.max() method.
10. set while condition to check the last element in deque's prefixSum value is bigger than the current prefixSum's value. since if it's bigger then it's useless, when subtract the deque's index prefixSum value, if it's bigger than current one then it will not produce the maxProfit candidate. so pop it out untill it's not bigger than the current one.
11. finally push the index into deque.
12. at the end return the maxProfit.

summary

Use monotonic deque to save the best possible maxProfit candidate's index in prefixSum array.