LeetCode 3689 - Maximum Total Subarray Value I

The problem asks us to select exactly k non-empty subarrays from a given integer array nums, where subarrays may overlap and can even be identical. For each chosen subarray nums[l..

leetcodemediumarraygreedy

LeetCode Problem 3689

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

Problem Understanding

The problem asks us to select exactly k non-empty subarrays from a given integer array nums, where subarrays may overlap and can even be identical. For each chosen subarray nums[l..r], we compute its value as the difference between its maximum and minimum element, specifically max(nums[l..r]) - min(nums[l..r]). The goal is to maximize the total sum of these values across all k chosen subarrays.

At first glance, this looks like a combinatorial optimization problem over all possible subarrays, which is potentially very large since there are O(n²) subarrays. However, the key structural insight is that each subarray’s value depends only on the global maximum and minimum within that subarray, and we are allowed to reuse the same subarray multiple times.

The constraints show that n can be up to 50,000 and k up to 100,000, which immediately rules out any O(n²) enumeration of subarrays. We need an O(n) or O(n log n) solution.

The important edge cases include arrays where all elements are equal (all subarray values become zero), arrays with a single element, and cases where the maximum and minimum occur at extreme positions.

Approaches

Brute Force Approach

The brute force strategy would enumerate every possible subarray [l, r], compute its maximum and minimum by scanning the segment, and track all values. After computing all subarray values, we would sort them and pick the top k.

This approach is correct because it directly evaluates the definition of the problem. However, computing max and min for each subarray costs O(n), and there are O(n²) subarrays, leading to an overall O(n³) time complexity, which is infeasible for large inputs.

Key Insight

A critical observation simplifies the problem dramatically. The value of any subarray is always bounded above by the global maximum of the array minus the global minimum of the array. This is because no subarray can contain values outside the array itself.

Let:

  • global_max = max(nums)
  • global_min = min(nums)

Then for any subarray:

max(subarray) ≤ global_max
min(subarray) ≥ global_min

So:

max(subarray) - min(subarray) ≤ global_max - global_min

This bound is achievable by choosing any subarray that includes both the global minimum and global maximum elements. Such a subarray will have value exactly global_max - global_min.

Since we are allowed to pick the same subarray multiple times, the optimal strategy is simply to pick this best subarray k times.

Thus, the problem reduces to computing the global range and multiplying by k.

Complexity Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Enumerates all subarrays and recomputes min/max
Optimal O(n) O(1) Uses global max/min and multiplies by k

Algorithm Walkthrough

The optimal algorithm is based on reducing the problem to a single global statistic computation.

  1. Scan through the array once to determine the minimum value in nums. This represents the smallest possible value that any subarray can contain.
  2. Scan through the array once to determine the maximum value in nums. This represents the largest possible value that any subarray can contain.
  3. Compute the maximum possible subarray value as global_max - global_min. This represents the best possible value achievable by any subarray in the entire array.
  4. Multiply this value by k, since we are allowed to reuse subarrays arbitrarily, including selecting the same optimal subarray multiple times.
  5. Return the resulting product as the final answer.

Why it works

The correctness comes from the fact that subarray values are entirely bounded by global extrema. Since any subarray is contained within the array, it cannot exceed the global maximum or go below the global minimum. Because repetition is allowed, we can always choose a subarray that achieves this bound k times, making it optimal.

Python Solution

from typing import List

class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        global_max = max(nums)
        global_min = min(nums)
        return (global_max - global_min) * k

The implementation directly computes the global maximum and minimum using built-in functions. It then computes their difference and multiplies by k. This corresponds exactly to the theoretical observation that all optimal subarrays achieve the same maximum possible value.

Go Solution

func maxTotalValue(nums []int, k int) int64 {
    if len(nums) == 0 {
        return 0
    }

    minVal := nums[0]
    maxVal := nums[0]

    for _, v := range nums {
        if v < minVal {
            minVal = v
        }
        if v > maxVal {
            maxVal = v
        }
    }

    return int64(k) * int64(maxVal-minVal)
}

In Go, we explicitly iterate through the slice to compute minimum and maximum values since there is no direct built-in equivalent to Python’s min and max for slices. We also cast to int64 to safely handle multiplication with k, avoiding potential overflow issues for larger intermediate results.

Worked Examples

Example 1

Input:

nums = [1, 3, 2], k = 2

We compute:

  • global_min = 1
  • global_max = 3
  • max subarray value = 3 - 1 = 2

Since k = 2:

total = 2 * 2 = 4

State progression:

Step global_min global_max result
scan nums 1 1 0
update 1 3 0
final 1 3 2 * k

Final answer is 4.

Example 2

Input:

nums = [4, 2, 5, 1], k = 3

We compute:

  • global_min = 1
  • global_max = 5
  • max subarray value = 4

Then:

total = 4 * 3 = 12

State progression:

Step global_min global_max
scan begins 4 4
see 2 2 4
see 5 2 5
see 1 1 5

Final result: 12.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass to compute minimum and maximum
Space O(1) Only a constant number of variables used

The algorithm is optimal because any solution must at least inspect all elements to determine global extrema.

Test Cases

assert Solution().maxTotalValue([1, 3, 2], 2) == 4  # basic example
assert Solution().maxTotalValue([4, 2, 5, 1], 3) == 12  # larger range
assert Solution().maxTotalValue([7], 10) == 0  # single element
assert Solution().maxTotalValue([5, 5, 5, 5], 100) == 0  # all equal
assert Solution().maxTotalValue([1, 1000000000], 1) == 999999999  # large gap
assert Solution().maxTotalValue([2, 1], 5) == 5  # reversed order max/min
Test Why
[1,3,2], k=2 validates basic computation
[4,2,5,1], k=3 verifies general case
[7], k=10 single-element edge case
all equal zero-value edge case
large gap stress large values
reversed order ensures order independence

Edge Cases

One important edge case is when the array has only one element. In this case, every subarray has both maximum and minimum equal to that element, resulting in a value of zero. The algorithm correctly returns zero since global_max - global_min = 0.

Another edge case occurs when all elements in the array are identical. Here again, every subarray has zero range, and the result remains zero regardless of k. The global extrema computation naturally handles this without special casing.

A third edge case involves very large values of nums[i] and large k. Since the result can grow up to 1e14 or more, using a 64-bit integer type in Go ensures correctness, while Python naturally handles arbitrary precision integers without overflow concerns.