LeetCode 3691 - Maximum Total Subarray Value II

LeetCode Problem 3691

Difficulty: 🔴 Hard
Topics: Array, Greedy, Segment Tree, Heap (Priority Queue)

Solution

Problem Understanding

The problem is asking us to select exactly k distinct subarrays from a given integer array nums such that the sum of their "values" is maximized. Each subarray's value is calculated as the difference between its maximum and minimum elements. Subarrays may overlap, but the exact same subarray (defined by the same start and end indices) cannot be chosen more than once.

The input consists of an array nums of length n and an integer k. The output is a single integer representing the maximum possible total value from selecting k subarrays. The constraints tell us that n can be as large as 50,000, so any naive approach that generates all subarrays (O(n²) or O(n³)) will be too slow. We also know that k can be up to 100,000, meaning we need a method that can efficiently determine the largest k subarray values without explicitly computing all of them.

Important edge cases include arrays where all elements are equal (the value of all subarrays is zero), arrays of length one (only one subarray exists), and cases where k is close to the maximum number of possible subarrays (n * (n + 1) / 2). These cases could trip up naive or memory-inefficient implementations.

Approaches

The brute-force approach would be to enumerate all subarrays, compute their values by finding the maximum and minimum in each subarray, store them, and then select the k largest values. This approach works correctly in principle but has time complexity O(n³) if max and min are computed separately for each subarray, or O(n²) if we use a sliding window or preprocessing technique. Even O(n²) is too slow for n = 50,000 because it results in ~2.5 billion operations.

The key insight for an optimal solution comes from the observation that the value of a subarray depends on its local maxima and minima. Using a monotonic stack, we can identify how many subarrays each element serves as a maximum or minimum. This lets us compute the "contribution" of each element to all subarrays efficiently. The largest contributions naturally correspond to the subarrays that produce the highest values. Using a priority queue (heap), we can then extract the k largest contributions without generating all subarrays explicitly.

Algorithm Walkthrough

1. Compute for each element the number of subarrays in which it is the maximum. Use a monotonic decreasing stack to efficiently find the "next greater element" and "previous greater element" indices. For element nums[i], the count of subarrays where it is the maximum is (i - prev_greater) * (next_greater - i).
2. Similarly, compute for each element the number of subarrays in which it is the minimum using a monotonic increasing stack. The count formula is the same: (i - prev_smaller) * (next_smaller - i).
3. For each element, compute its total contribution to the sum of subarray values: value_contrib[i] = nums[i] * (count_as_max - count_as_min). This represents the net contribution across all subarrays.
4. Store all these contributions in a max-heap (priority queue). Pop the top k contributions, which correspond to the highest possible subarray values.
5. Sum the top k contributions and return the result.

Why it works: Each subarray's value is determined by the difference between the maximum and minimum elements. By counting in how many subarrays each element is max or min, and taking the net effect, we ensure that the contributions are counted exactly once per subarray. Selecting the top k contributions guarantees the maximal total value because any other subarray combination would yield smaller contributions.

Python Solution

from typing import List
import heapq

class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        n = len(nums)
        
        # Monotonic stack to find previous and next greater for each element
        prev_greater, next_greater = [-1] * n, [n] * n
        stack = []
        for i in range(n):
            while stack and nums[stack[-1]] < nums[i]:
                idx = stack.pop()
                next_greater[idx] = i
            if stack:
                prev_greater[i] = stack[-1]
            stack.append(i)
        
        # Monotonic stack to find previous and next smaller for each element
        prev_smaller, next_smaller = [-1] * n, [n] * n
        stack = []
        for i in range(n):
            while stack and nums[stack[-1]] > nums[i]:
                idx = stack.pop()
                next_smaller[idx] = i
            if stack:
                prev_smaller[i] = stack[-1]
            stack.append(i)
        
        # Compute contributions
        contributions = []
        for i in range(n):
            max_count = (i - prev_greater[i]) * (next_greater[i] - i)
            min_count = (i - prev_smaller[i]) * (next_smaller[i] - i)
            net_contrib = nums[i] * (max_count - min_count)
            contributions.append(net_contrib)
        
        # Select top k contributions
        return sum(heapq.nlargest(k, contributions))

Implementation Explanation:

The solution uses monotonic stacks to calculate how many subarrays each element is the maximum or minimum, avoiding the need to enumerate all subarrays. The net contribution of each element is stored in a list. Using heapq.nlargest(k, ...), we efficiently select the top k values for the maximal total. This reduces the time complexity from O(n²) to O(n log n) due to the heap operation.

Go Solution

package main

import (
    "container/heap"
)

func maxTotalValue(nums []int, k int) int64 {
    n := len(nums)
    prevGreater, nextGreater := make([]int, n), make([]int, n)
    prevSmaller, nextSmaller := make([]int, n), make([]int, n)
    for i := range prevGreater {
        prevGreater[i] = -1
        nextGreater[i] = n
        prevSmaller[i] = -1
        nextSmaller[i] = n
    }

    stack := []int{}
    for i := 0; i < n; i++ {
        for len(stack) > 0 && nums[stack[len(stack)-1]] < nums[i] {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            nextGreater[idx] = i
        }
        if len(stack) > 0 {
            prevGreater[i] = stack[len(stack)-1]
        }
        stack = append(stack, i)
    }

    stack = []int{}
    for i := 0; i < n; i++ {
        for len(stack) > 0 && nums[stack[len(stack)-1]] > nums[i] {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            nextSmaller[idx] = i
        }
        if len(stack) > 0 {
            prevSmaller[i] = stack[len(stack)-1]
        }
        stack = append(stack, i)
    }

    contrib := []int64{}
    for i := 0; i < n; i++ {
        maxCount := int64((i - prevGreater[i]) * (nextGreater[i] - i))
        minCount := int64((i - prevSmaller[i]) * (nextSmaller[i] - i))
        net := int64(nums[i]) * (maxCount - minCount)
        contrib = append(contrib, net)
    }

    h := &IntHeap{}
    heap.Init(h)
    for _, v := range contrib {
        heap.Push(h, v)
    }

    total := int64(0)
    for i := 0; i < k && h.Len() > 0; i++ {
        total += heap.Pop(h).(int64)
    }
    return total
}

type IntHeap []int64

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int64)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

Go-Specific Notes:

Go requires using a heap interface to maintain a max-heap, unlike Python's built-in heapq. Integer overflow is handled by using int64 for counts and contributions. Slice indexing and initialization ensure that edge cases (like empty stack) are correctly handled.

Worked Examples

**Example 1