# Maximum and Minimum Sums of at Most Size K Subarrays
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-and-minimum-sums-of-at-most-size-k-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/maximum-and-minimum-sums-of-at-most-size-k-subarrays
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array, Stack, Monotonic Stack
---
## Problem
You are given an integer array `nums` and a **positive** integer `k`. Return the sum of the **maximum** and **minimum** elements of all subarrays with **at most** `k` elements.

**Example 1:**

**Input:** nums = \[1,2,3\], k = 2

**Output:** 20

**Explanation:**

The subarrays of `nums` with at most 2 elements are:

| **Subarray**    | Minimum | Maximum | Sum |
| --------------- | ------- | ------- | --- |
| \[1\]           | 1       | 1       | 2   |
| \[2\]           | 2       | 2       | 4   |
| \[3\]           | 3       | 3       | 6   |
| \[1, 2\]        | 1       | 2       | 3   |
| \[2, 3\]        | 2       | 3       | 5   |
| **Final Total** |         |         | 20  |

The output would be 20.

**Example 2:**

**Input:** nums = \[1,-3,1\], k = 2

**Output:** \-6

**Explanation:**

The subarrays of `nums` with at most 2 elements are:

| **Subarray**    | Minimum | Maximum | Sum |
| --------------- | ------- | ------- | --- |
| \[1\]           | 1       | 1       | 2   |
| \[-3\]          | \-3     | \-3     | \-6 |
| \[1\]           | 1       | 1       | 2   |
| \[1, -3\]       | \-3     | 1       | \-2 |
| \[-3, 1\]       | \-3     | 1       | \-2 |
| **Final Total** |         |         | \-6 |

The output would be -6.

**Constraints:**

* `1 <= nums.length <= 80000`
* `1 <= k <= nums.length`
* `-106 <= nums[i] <= 106`

# Approaches
## Brute Force with Optimization
This approach involves iterating through all possible subarrays that satisfy the length constraint (at most `k`). For each starting position `i`, we extend the subarray to the right, one element at a time, up to a length of `k`. While extending, we keep track of the minimum and maximum values seen so far in the current subarray and add them to a running total.
**Time:** O(n * k), where `n` is the number of elements in `nums`. The outer loop runs `n` times, and the inner loop runs at most `k` times. Inside the inner loop, operations are O(1). · **Space:** O(1) extra space, as we only use a few variables to store the running sum and current min/max.
**Pros:** Simple to understand and implement.; Uses constant extra space.
**Cons:** The time complexity of O(n*k) is too slow for the given constraints, where n and k can be up to 80,000. This will result in a Time Limit Exceeded (TLE) error on most platforms.
### Explanation
The brute-force method is the most straightforward way to solve the problem. We generate every single subarray, check if its length is at most `k`, and if so, find its minimum and maximum elements to add to our total sum.

A slight optimization on the naive brute-force method is to avoid re-calculating the minimum and maximum for each subarray. When we consider subarrays starting at index `i`, we can iterate with a second pointer `j` from `i` outwards. As we expand the subarray `nums[i..j]` by incrementing `j`, we can update the minimum and maximum in O(1) time.

```java
class Solution {
    public long findMaximumsAndMinimums(int[] nums, int k) {
        long totalSum = 0;
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            int currentMin = Integer.MAX_VALUE;
            int currentMax = Integer.MIN_VALUE;
            // Iterate through all subarrays starting at i with length at most k
            for (int j = i; j < n && (j - i + 1) <= k; j++) {
                // Update min and max for the subarray nums[i..j]
                currentMin = Math.min(currentMin, nums[j]);
                currentMax = Math.max(currentMax, nums[j]);
                
                // Add the min and max of the current subarray to the total sum
                totalSum += (long)currentMin + currentMax;
            }
        }

        return totalSum;
    }
}
```
### Algorithm
1. Initialize a variable `totalSum` to 0.
2. Use a nested loop to generate all subarrays. The outer loop iterates from `i = 0` to `n-1` to select the starting index of the subarray.
3. The inner loop iterates from `j = i` to `n-1` to select the ending index.
4. Inside the inner loop, check if the length of the current subarray `(j - i + 1)` is greater than `k`. If it is, break the inner loop as subsequent subarrays starting at `i` will also be too long.
5. For each valid subarray `nums[i..j]`, we need to find its minimum and maximum elements. Instead of re-calculating this from scratch for each subarray, we can maintain the minimum and maximum of the subarray `nums[i..j]` as we extend it from `j` to `j+1`.
6. For a fixed `i`, initialize `currentMin = nums[i]` and `currentMax = nums[i]`. 
7. As `j` increases, update `currentMin = min(currentMin, nums[j])` and `currentMax = max(currentMax, nums[j])`.
8. Add the `currentMin` and `currentMax` to `totalSum`.
9. After iterating through all possible subarrays, return `totalSum`.

## Monotonic Stack and Contribution of Each Element
A much more efficient approach is to change perspective. Instead of iterating through subarrays, we can iterate through each element `nums[i]` and calculate its total contribution to the final sum. The problem can be split into two parts: finding the sum of all maximums and the sum of all minimums. The logic is symmetrical, so we'll focus on the maximums.

The contribution of `nums[i]` to the sum of maximums is `nums[i]` multiplied by the number of subarrays (of length at most `k`) in which `nums[i]` is the maximum element. We can use a monotonic stack to efficiently find the nearest elements to the left and right of `i` that are larger than `nums[i]`. This defines a range where `nums[i]` is the maximum. Within this range, we can then use a mathematical formula to count how many subarrays satisfy the length constraint `k` in O(1) time. This leads to an overall linear time solution.
**Time:** O(n). Finding the left and right boundaries for all elements using a monotonic stack takes O(n). The final loop to calculate contributions also runs `n` times, with O(1) work inside. Thus, the total time complexity is linear. · **Space:** O(n) to store the `left` and `right` boundary arrays and for the stack used in their computation.
**Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; The core logic of contribution and monotonic stacks is a powerful pattern applicable to many other problems.
**Cons:** The logic is significantly more complex than the brute-force approach.; The implementation requires careful handling of edge cases and the logic for counting subarrays, which can be error-prone.; Requires O(n) extra space for stacks and boundary arrays.
### Explanation
This approach hinges on calculating the contribution of each element `nums[i]` separately for the sum of maximums and the sum of minimums.

Let's define a helper function `calculateContribution(nums, k, isMax)`.

**1. Finding Boundaries with a Monotonic Stack:**
To find the number of subarrays where `nums[i]` is the maximum, we need to find its effective range. We find `left[i]`, the index of the first element to the left of `i` that is strictly greater than `nums[i]`, and `right[i]`, the index of the first element to the right that is greater than or equal to `nums[i]`. This can be done for all `i` in O(n) using a monotonic decreasing stack. A similar process with a monotonic increasing stack is used for minimums.

**2. Calculating Contribution:**
Once we have `left[i]` and `right[i]`, we know that `nums[i]` is the maximum for any subarray `nums[l..r]` where `left[i] < l <= i` and `i <= r < right[i]`. Let `x = i - left[i]` be the number of possible start positions to the left (including `i`) and `y = right[i] - i` be the number of possible end positions to the right (including `i`).

We now need to count the pairs `(l, r)` that also satisfy `r - l + 1 <= k`. This can be done with an O(1) formula derived from summing up the possibilities. For each possible number of elements to the left of `i`, `p` (from 0 to `x-1`), we count the valid number of elements to the right, `q` (from 0 to `y-1`), such that `p + q + 1 <= k`. The total count for `nums[i]` is `sum_{p=0 to x-1} min(y, k-p)`. This sum can be computed in O(1) by splitting it into an arithmetic series and a constant part.

**3. Final Sum:**
The final answer is `calculateContribution(nums, k, true) + calculateContribution(nums, k, false)`.

```java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public long findMaximumsAndMinimums(int[] nums, int k) {
        long sumMax = calculateContribution(nums, k, true);
        long sumMin = calculateContribution(nums, k, false);
        return sumMax + sumMin;
    }

    private long calculateContribution(int[] nums, int k, boolean isMax) {
        int n = nums.length;
        int[] left = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        // To ensure each subarray's max/min is counted once, we use a strict inequality
        // on one side and a non-strict one on the other for tie-breaking.
        // For max: left is next >, right is next >=.
        // For min: left is next <, right is next <=.

        // Left boundary (strict)
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && 
                   (isMax ? nums[stack.peek()] <= nums[i] : nums[stack.peek()] >= nums[i])) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        int[] right = new int[n];
        stack.clear();

        // Right boundary (non-strict)
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && 
                   (isMax ? nums[stack.peek()] < nums[i] : nums[stack.peek()] > nums[i])) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }

        long totalContribution = 0;
        for (int i = 0; i < n; i++) {
            long x = i - left[i];
            long y = right[i] - i;

            // Count valid subarrays where nums[i] is the extremum.
            // This is equivalent to counting pairs (p, q) where 0<=p<x, 0<=q<y and p+q+1 <= k.
            // The formula is: sum_{p=0 to x-1} min(y, k-p)
            long count = 0;
            long p_split = k - y;

            if (p_split >= x) { // k >= x+y, all x*y subarrays are valid
                count = x * y;
            } else {
                // Part 1: p from 0 to p_split-1. Here, k-p > y, so min(y, k-p) = y.
                if (p_split > 0) {
                    count += p_split * y;
                }
                // Part 2: p from max(0, p_split) to x-1. Here, k-p <= y, so min(y, k-p) = k-p.
                // This is an arithmetic series sum.
                long start_p = Math.max(0, p_split);
                long num_terms = x - start_p;
                if (num_terms > 0) {
                    long first_term = k - start_p;
                    long last_term = k - (x - 1);
                    count += num_terms * (first_term + last_term) / 2;
                }
            }
            totalContribution += (long)nums[i] * count;
        }
        return totalContribution;
    }
}
```
### Algorithm
1. Decompose the problem into two independent subproblems: calculating the sum of maximums of all valid subarrays, and the sum of minimums of all valid subarrays. The final answer is the sum of these two results.
2. Let's focus on the sum of maximums. Instead of iterating over subarrays, we iterate through each element `nums[i]` and calculate its total contribution. The contribution of `nums[i]` is `nums[i]` multiplied by the number of valid subarrays for which `nums[i]` is the maximum.
3. To count these subarrays, we first need to find the range `(L, R)` in which `nums[i]` is the maximum. `L` is the index of the first element to the left of `i` that is greater than `nums[i]`, and `R` is the index of the first element to the right of `i` that is greater than or equal to `nums[i]`. This specific tie-breaking (using `>` on one side and `>=` on the other) ensures that for any subarray, the maximum element is counted exactly once. These `L` and `R` boundaries can be found for all `i` in O(n) time using a monotonic stack.
4. For a fixed `i`, `nums[i]` is the maximum for any subarray `nums[l..r]` where `L < l <= i` and `i <= r < R`. We also have the constraint that the subarray length `r - l + 1 <= k`.
5. Let `x = i - L` and `y = R - i`. These are the number of possible start positions (relative to `i`) and end positions, respectively. We need to count pairs of `(l, r)` satisfying the conditions. This can be formulated as a counting problem that can be solved with a derived mathematical formula in O(1) time for each `i`.
6. The number of valid subarrays for `nums[i]` as max is `count = sum_{p=0 to x-1} (min(y, k-p))`. This sum can be calculated in O(1) by splitting it into two parts: one where `k-p >= y` and one where `k-p < y`.
7. Sum up the contributions `nums[i] * count` for all `i` to get the total sum of maximums.
8. Repeat a symmetrical process for the sum of minimums (e.g., finding next smaller elements) and add the results.

# Solutions
### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} k * @return {number} */ var minMaxSubarraySum = function ( nums , k ) { const computeSum = ( nums , k , isMin ) => { const n = nums . length ; const prev = Array ( n ). fill ( - 1 ); const next = Array ( n ). fill ( n ); let stk = []; if ( isMin ) { for ( let i = 0 ; i < n ; i ++ ) { while ( stk . length > 0 && nums [ stk [ stk . length - 1 ]] >= nums [ i ]) { stk . pop (); } prev [ i ] = stk . length > 0 ? stk [ stk . length - 1 ] : - 1 ; stk . push ( i ); } stk = []; for ( let i = n - 1 ; i >= 0 ; i -- ) { while ( stk . length > 0 && nums [ stk [ stk . length - 1 ]] > nums [ i ]) { stk . pop (); } next [ i ] = stk . length > 0 ? stk [ stk . length - 1 ] : n ; stk . push ( i ); } } else { for ( let i = 0 ; i < n ; i ++ ) { while ( stk . length > 0 && nums [ stk [ stk . length - 1 ]] <= nums [ i ]) { stk . pop (); } prev [ i ] = stk . length > 0 ? stk [ stk . length - 1 ] : - 1 ; stk . push ( i ); } stk = []; for ( let i = n - 1 ; i >= 0 ; i -- ) { while ( stk . length > 0 && nums [ stk [ stk . length - 1 ]] < nums [ i ]) { stk . pop (); } next [ i ] = stk . length > 0 ? stk [ stk . length - 1 ] : n ; stk . push ( i ); } } let totalSum = 0 ; for ( let i = 0 ; i < n ; i ++ ) { const left = prev [ i ]; const right = next [ i ]; const a = left + 1 ; const b = i ; const c = i ; const d = right - 1 ; let start1 = Math . max ( a , i - k + 1 ); let endCandidate1 = d - k + 1 ; let upper1 = Math . min ( b , endCandidate1 ); let sum1 = 0 ; if ( upper1 >= start1 ) { const termCount = upper1 - start1 + 1 ; const first = start1 ; const last = upper1 ; const indexSum = ( last * ( last + 1 )) / 2 - (( first - 1 ) * first ) / 2 ; const constantSum = ( k - i ) * termCount ; sum1 = indexSum + constantSum ; } let start2 = upper1 + 1 ; let end2 = b ; start2 = Math . max ( start2 , a ); end2 = Math . min ( end2 , b ); let sum2 = 0 ; if ( start2 <= end2 ) { const count = end2 - start2 + 1 ; const term = d - i + 1 ; sum2 = term * count ; } totalSum += nums [ i ] * ( sum1 + sum2 ); } return totalSum ; }; const minSum = computeSum ( nums , k , true ); const maxSum = computeSum ( nums , k , false ); return minSum + maxSum ; };
```