3691. Maximum Total Subarray Value II

  • Array
  • Heap (Priority Queue)
  • Sparse Table
TIME
O(n log n + k log k)
SPACE
O(n log n + k)
problem on leetcode ↗source on github ↗

Intuition

We want the k distinct subarrays with the largest values, then sum those values. The crucial structural fact: shrinking a subarray can never increase its value. Removing an element from either end can only lower the max or raise the min, so

value([l, r]) >= value([l+1, r])  and  value([l, r]) >= value([l, r-1])

Therefore the whole array [0, n-1] has the maximum value of all subarrays, and every subarray is reachable from it by repeatedly trimming one end, with value non-increasing along the way. This is exactly the setting where a best-first (Dijkstra-like) heap extraction yields elements in non-increasing value order.

Approach

  1. Build sparse tables for range maximum and range minimum so any subarray value max(l..r) - min(l..r) can be queried in O(1).
  2. Push the full array [0, n-1] into a max-heap keyed by value; mark it visited.
  3. Repeat k times:
    • Pop the interval with the largest value and add that value to the answer.
    • Generate its two "children" by trimming one end: [l+1, r] and [l, r-1].
    • For each valid, not-yet-visited child, compute its value and push it, marking it visited (a child has two possible parents, so the visited set prevents pushing duplicates).
  4. After k pops, the accumulated sum is the maximum total value.

Because every interval's value dominates its children and the root is the unique maximum, the heap pops the global top-k values in order.

Complexity

  • Time: O(n log n + k log k), sparse table build plus k heap operations, each with O(1) value queries
  • Space: O(n log n + k), sparse tables and the heap/visited frontier

Edge Cases

  • All elements equal -> every value is 0, answer is 0
  • n == 1 -> only one subarray (value 0), and k is forced to 1
  • Large values and large k -> totals can reach ~`10^14`, so use 64-bit integers in Java
  • A child interval reachable from two parents -> visited set ensures it is counted once

Code

import heapq
from typing import List


class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        """
        3691. Maximum Total Subarray Value II
        Time: O(n log n + k log k)
        Space: O(n log n + k)
        """
        n = len(nums)

        # Sparse tables for range max and range min (O(1) queries).
        log = [0] * (n + 1)
        for i in range(2, n + 1):
            log[i] = log[i // 2] + 1

        levels = log[n] + 1
        sparse_max = [nums[:]]
        sparse_min = [nums[:]]
        for j in range(1, levels):
            half = 1 << (j - 1)
            prev_max = sparse_max[j - 1]
            prev_min = sparse_min[j - 1]
            length = n - (1 << j) + 1
            sparse_max.append(
                [max(prev_max[i], prev_max[i + half]) for i in range(length)]
            )
            sparse_min.append(
                [min(prev_min[i], prev_min[i + half]) for i in range(length)]
            )

        def value(l: int, r: int) -> int:
            j = log[r - l + 1]
            offset = r - (1 << j) + 1
            hi = max(sparse_max[j][l], sparse_max[j][offset])
            lo = min(sparse_min[j][l], sparse_min[j][offset])
            return hi - lo

        # Best-first extraction: each interval's value dominates its children,
        # so popping k times yields the k largest subarray values.
        heap = [(-value(0, n - 1), 0, n - 1)]
        visited = {(0, n - 1)}
        total = 0

        for _ in range(k):
            neg_val, l, r = heapq.heappop(heap)
            total += -neg_val

            if l + 1 <= r and (l + 1, r) not in visited:
                visited.add((l + 1, r))
                heapq.heappush(heap, (-value(l + 1, r), l + 1, r))

            if l <= r - 1 and (l, r - 1) not in visited:
                visited.add((l, r - 1))
                heapq.heappush(heap, (-value(l, r - 1), l, r - 1))

        return total