Maximum Constrained Subarray Sum under Arithmetic Range Updates
You are given an initial array $A$ of size $N$ and $M$ update operations. Each update operation is represented as $[L, R, A_0, D]$, indicating that an arithmetic progression is added to the subarray $A[L..R]$ ($0 \le L \le R < N$). Specifically, for each index $i$ in the range $[L, R]$, $A[i]$ is increased by $A_0 + (i - L) \times D$.
After applying all $M$ updates to the array $A$, you are asked to find the maximum sum of any contiguous subarray whose length $L$ satisfies $K_{\min} \le L \le K_{\max}$.
To achieve optimal performance, you should process all arithmetic range updates in $O(1)$ time per update using second-order difference arrays, and then determine the length-constrained maximum subarray sum in $O(N)$ time using prefix sums combined with a sliding window deque.
[ "5", "[0, 0, 0, 0, 0]", "[[0, 3, 1, 2]]", "2", "3" ]
Explanation. Applying update [0, 3, 1, 2] adds [1, 3, 5, 7] to indices 0..3. Array becomes [1, 3, 5, 7, 0]. Subarrays of length 2 or 3: [1, 3] (sum 4), [3, 5] (sum 8), [5, 7] (sum 12), [1, 3, 5] (sum 9), [3, 5, 7] (sum 15), [5, 7, 0] (sum 12). Maximum sum is 15.
[ "6", "[-2, 1, 3, -1, 4, -5]", "[[1, 4, 2, -1], [0, 2, 3, 3]]", "1", "4" ]
Explanation. Update 1 adds [2, 1, 0, -1] to indices 1..4. Update 2 adds [3, 6, 9] to indices 0..2. Final array is [1, 9, 13, -1, 3, -5]. Maximum sum of length between 1 and 4 is subarray A[1..4] = 9 + 13 - 1 + 3 = 24.
[ "4", "[-10, -20, -30, -40]", "[]", "1", "2" ]
Explanation. With no updates, array remains [-10, -20, -30, -40]. The maximum sum of length 1 or 2 is -10 (the single element A[0]).
[ "8", "[1, -5, 2, 4, -3, 6, -1, 0]", "[[0, 7, 10, -2], [2, 5, -5, 5]]", "3", "5" ]
Explanation. After processing both arithmetic updates, array becomes [11, 3, 3, 8, 4, 16, -3, -4]. For lengths between 3 and 5, subarray A[1..5] has length 5 and sum 3 + 3 + 8 + 4 + 16 = 34, which is the maximum.
Follow-up: How would you answer range queries dynamically if updates and queries were interleaved online? Consider how dynamic segment trees with lazy propagation handling linear functions could be utilized.
$1 \le N \le 10^5$ $0 \le M \le 10^5$ $0 \le L \le R < N$ $1 \le K_{\min} \le K_{\max} \le N$ $-10^6 \le A[i], A_0, D \le 10^6$
- Views
- 13