3689. Maximum Total Subarray Value I

MediumGreedyArray

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums of length n and an integer k.

You need to choose exactly k non-empty subarrays nums[l..r] from nums. There are two important rules about how you can pick them:

Subarrays may overlap with each other.
The exact same subarray (with the same l and r) can be chosen more than once.

The value of a single subarray nums[l..r] is defined as the difference between its largest and smallest elements:

max(nums[l..r]) - min(nums[l..r])

The total value is the sum of the values of all k chosen subarrays.

Your task is to return the maximum possible total value you can achieve.

For example, if nums = [1, 3, 2] and k = 2, you could pick the subarray [1, 3, 2] twice. Its value is 3 - 1 = 2, so the total value is 2 + 2 = 4, which is the best possible answer here.

Key points to notice:

Since repetition is allowed, you can simply pick the single best subarray k times.
The best possible value of any subarray is bounded by the difference between the global maximum and global minimum of the entire array, and the full array nums[0..n-1] itself always achieves this value.
Therefore, the answer is k * (max(nums) - min(nums)).

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Greedy Algorithms?

This problem maps to Greedy Algorithms through a short path in the full flowchart.

The total value is maximized by picking the subarray with the greatest max-minus-min difference k times; the full array always achieves the global max-min difference.

Open in Flowchart

Intuition

At first glance, this problem looks like it might require some complex strategy: choosing k subarrays out of all possible O(n^2) candidates to maximize a sum. But two observations collapse the entire problem into a one-line answer.

Observation 1: Repetition removes the need for variety.

Since the problem explicitly allows us to pick the exact same subarray multiple times, there is no benefit in diversifying our choices. If one subarray has the highest value among all subarrays, the optimal strategy is simply to pick that single best subarray k times. The total value then becomes k * (best subarray value).

So the question reduces to: what is the maximum value any single subarray can have?

Observation 2: The whole array is always the best (or tied for best) subarray.

The value of a subarray is max(nums[l..r]) - min(nums[l..r]). Notice two things:

No subarray can have a value greater than max(nums) - min(nums), because any subarray's maximum is at most the global maximum, and its minimum is at least the global minimum.
The full array nums[0..n-1] is itself a valid subarray, and it achieves exactly this value, since it contains both the global maximum and the global minimum.

In other words, expanding a subarray can never decrease its value — the max can only stay the same or grow, and the min can only stay the same or shrink. So the widest possible subarray (the entire array) is guaranteed to be optimal.

Putting it together.

The best single subarray has value max(nums) - min(nums), and we should pick it k times. The answer is therefore:

k * (max(nums) - min(nums))

This turns what looks like a combinatorial optimization problem into a simple scan for the global maximum and minimum.

Pattern Learn more about Greedy patterns.

Solution Approach

Simple Observation

Based on the intuition, the implementation requires no special algorithms or data structures — just two linear scans over the array.

Steps:

Find the global maximum of the array using max(nums). This is the largest value any subarray's maximum can ever be.
Find the global minimum of the array using min(nums). This is the smallest value any subarray's minimum can ever be.
Compute the best single subarray value as max(nums) - min(nums). The full array nums[0..n-1] is a valid subarray that achieves exactly this value, so it is attainable.
Multiply by k, since we are allowed to choose the same subarray k times. The final answer is k * (max(nums) - min(nums)).

Implementation:

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

The entire solution fits in a single expression. Python's built-in max() and min() each perform one pass over the array, and the rest is constant-time arithmetic.

Why this is correct:

Upper bound: For any subarray nums[l..r], we have max(nums[l..r]) <= max(nums) and min(nums[l..r]) >= min(nums), so its value is at most max(nums) - min(nums). Summing over k choices, the total value is at most k * (max(nums) - min(nums)).
Achievability: Choosing the full array k times reaches exactly this bound.

Since the upper bound is achievable, it is the answer.

Complexity Analysis:

Time complexity: O(n), where n is the length of nums. We scan the array a constant number of times to find the maximum and minimum.
Space complexity: O(1), as only a constant amount of extra space is used.

Example Walkthrough

Let's trace through the solution with nums = [4, 1, 7, 2] and k = 3.

Step 1: Find the global maximum.

Scanning the array: max(nums) = 7 (located at index 2). No subarray can ever have a maximum larger than this.

Step 2: Find the global minimum.

Scanning the array again: min(nums) = 1 (located at index 1). No subarray can ever have a minimum smaller than this.

Step 3: Compute the best single subarray value.

The best possible value of any single subarray is:

max(nums) - min(nums) = 7 - 1 = 6

Is this value actually attainable? Yes — the full array nums[0..3] = [4, 1, 7, 2] contains both 7 and 1, so its value is exactly 7 - 1 = 6.

To confirm no other subarray does better, consider a few candidates:

Subarray	Max	Min	Value
`[4, 1]`	4	1	3
`[1, 7]`	7	1	6
`[7, 2]`	7	2	5
`[4, 1, 7]`	7	1	6
`[4, 1, 7, 2]`	7	1	6

Every subarray's value is capped at 6, and any subarray containing both index 1 and index 2 achieves it. The full array is always one such subarray.

Step 4: Multiply by k.

Since the same subarray can be chosen repeatedly, the optimal strategy is to pick [1, 7] (or the full array — either works) all 3 times:

total = 3 × 6 = 18

So the answer is k * (max(nums) - min(nums)) = 3 * (7 - 1) = 18.

Notice how there is no need to enumerate all O(n²) subarrays or carefully mix different choices — the repetition rule means one best subarray, taken k times, is always optimal, and that best value is simply the spread between the global maximum and minimum.

Solution Implementation

1class Solution:
2    def maxTotalValue(self, nums: List[int], k: int) -> int:
3        # The value of any subarray is defined as (max element - min element).
4        # The maximum possible value across all subarrays is achieved by the
5        # subarray that contains both the global maximum and global minimum
6        # of the entire array (e.g., the whole array itself).
7
8        # Find the global maximum and minimum of the array.
9        max_value = max(nums)
10        min_value = min(nums)
11
12        # The largest achievable difference for any single subarray.
13        max_difference = max_value - min_value
14
15        # Since we can pick the same (or overlapping) optimal subarray k times,
16        # the answer is simply k multiplied by the maximum difference.
17        return k * max_difference
18```
19
20**Explanation of the approach:**
21
221. **Key observation**: A subarray's value is `max - min`. The largest possible value is `max(nums) - min(nums)`, achievable by choosing the entire array (or any subarray spanning both extremes).
23
242. **Greedy choice**: To maximize the total over `k` selections, pick that optimal subarray every time, giving `k * (max(nums) - min(nums))`.
25
263. **Complexity**: Time is `O(n)` for the two linear scans (`max` and `min`), and space is `O(1)`.
27
28**Alternative perspective**: A single pass could compute both extremes simultaneously, slightly reducing constant factors:
29
30```python3
31class Solution:
32    def maxTotalValue(self, nums: List[int], k: int) -> int:
33        # Track both extremes in one traversal.
34        max_value = min_value = nums[0]
35        for num in nums:
36            if num > max_value:
37                max_value = num
38            elif num < min_value:
39                min_value = num
40        return k * (max_value - min_value)
41

1class Solution {
2    public long maxTotalValue(int[] nums, int k) {
3        // Initialize trackers for the maximum and minimum values in the array.
4        // maxValue starts at 0 (assuming non-negative inputs),
5        // minValue starts at a large sentinel value (2^30).
6        int maxValue = 0;
7        int minValue = 1 << 30;
8
9        // Single pass through the array to find the global maximum and minimum.
10        for (int num : nums) {
11            maxValue = Math.max(maxValue, num);
12            minValue = Math.min(minValue, num);
13        }
14
15        // The largest possible value of any subarray is (globalMax - globalMin),
16        // achieved by a subarray spanning both extremes.
17        // Selecting that subarray k times yields the maximum total value.
18        // Multiply by 1L to avoid integer overflow before the result is widened to long.
19        return 1L * k * (maxValue - minValue);
20    }
21}
22

1class Solution {
2public:
3    long long maxTotalValue(vector<int>& nums, int k) {
4        // Find both the minimum and maximum elements of the array
5        // in a single pass using minmax_element.
6        // minIt points to the smallest element, maxIt points to the largest.
7        auto [minIt, maxIt] = minmax_element(nums.begin(), nums.end());
8
9        // The maximum possible value of (max - min) over any subarray
10        // is achieved by the subarray covering the global max and min,
11        // i.e., the entire array's range: (*maxIt - *minIt).
12        //
13        // Since we can choose the same subarray multiple times,
14        // the answer is simply k times this maximum range.
15        //
16        // Multiply by 1LL to promote the computation to long long
17        // and avoid potential integer overflow.
18        return 1LL * k * (*maxIt - *minIt);
19    }
20};
21```
22
23**Explanation of the approach:**
24
251. **Key observation:** The value of any subarray is defined as `max(subarray) - min(subarray)`. The largest achievable value comes from a subarray that contains both the global maximum and global minimum of `nums` — for example, the whole array itself. So the best single value is `globalMax - globalMin`.
26
272. **Greedy choice:** Since subarrays can be selected repeatedly (k times), picking the optimal subarray every time yields `k * (globalMax - globalMin)`.
28
293. **Complexity:**
30   - Time: `O(n)` — one linear scan via `minmax_element`.
31   - Space: `O(1)` — only iterators and constants are used.
32
33**Alternative perspective:** You could also compute the min and max with an explicit loop, which avoids structured bindings if older C++ standards are required:
34
35```cpp
36class Solution {
37public:
38    long long maxTotalValue(vector<int>& nums, int k) {
39        int minVal = nums[0], maxVal = nums[0];
40        // Manually track the minimum and maximum values.
41        for (int num : nums) {
42            minVal = min(minVal, num);
43            maxVal = max(maxVal, num);
44        }
45        // The best subarray value, taken k times.
46        return 1LL * k * (maxVal - minVal);
47    }
48};
49

1/**
2 * Calculates the maximum total value by selecting k subarrays,
3 * where each subarray's value is the difference between its
4 * maximum and minimum elements.
5 *
6 * Key insight: the subarray covering the entire array yields the
7 * largest possible value, which is (global max - global min).
8 * Therefore, picking that subarray k times gives the answer.
9 *
10 * @param nums - The input array of numbers
11 * @param k - The number of subarrays to select
12 * @returns The maximum total value achievable
13 */
14function maxTotalValue(nums: number[], k: number): number {
15    // Find the minimum element in the array
16    const minValue: number = Math.min(...nums);
17
18    // Find the maximum element in the array
19    const maxValue: number = Math.max(...nums);
20
21    // The best single subarray value is (maxValue - minValue),
22    // so selecting it k times yields k * (maxValue - minValue)
23    return k * (maxValue - minValue);
24}
25

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums. The code computes max(nums) and min(nums), each of which requires a single linear scan through the array, taking O(n) time. The final multiplication and subtraction are constant-time operations, so the overall time complexity is O(n) + O(n) + O(1) = O(n).
Space Complexity: O(1). The code only uses a constant amount of extra space to store the intermediate results of max(nums), min(nums), and the final computed value, regardless of the input size.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Assuming the `k` subarrays must be distinct

The pitfall: The most frequent mistake is misreading the problem and assuming each chosen subarray must have a unique (l, r) pair. This sends solvers down a much harder path: enumerating all O(n²) subarrays, computing each one's max - min value (often with a sparse table or monotonic deques), and then summing the top k values via a heap or sorting.

# Overcomplicated (and unnecessary) approach born from this misreading:
class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        values = []
        n = len(nums)
        for l in range(n):                      # O(n^2) subarrays
            cur_max = cur_min = nums[l]
            for r in range(l, n):
                cur_max = max(cur_max, nums[r])
                cur_min = min(cur_min, nums[r])
                values.append(cur_max - cur_min)
        values.sort(reverse=True)               # O(n^2 log n)
        return sum(values[:k])                  # Wrong premise AND too slow

For large n, this is O(n²) time and memory at best — guaranteed TLE/MLE — and it doesn't even match the problem statement.

The solution: Read the rules carefully: "The exact same subarray can be chosen more than once." Repetition is explicitly allowed, so the single best subarray can be picked all k times. The answer collapses to one line:

return k * (max(nums) - min(nums))

2. Believing the optimal subarray must be searched for

The pitfall: Even after noticing repetition is allowed, some solvers still try to find the best subarray — e.g., scanning windows or trying to locate the positions of the extremes and checking whether a "valid" subarray connects them. This adds needless logic and potential bugs (off-by-one boundaries, wrong window handling).

The solution: No search is needed. Two facts settle it:

Upper bound: any subarray's max is ≤ max(nums) and its min is ≥ min(nums), so its value is ≤ max(nums) - min(nums).
Achievability: the full array nums[0..n-1] always contains both global extremes, so it attains the bound exactly.

Since the upper bound is always achievable, no positional reasoning about where the max and min live is required.

3. Integer overflow when porting to other languages

The pitfall: Python integers are arbitrary precision, so k * (max - min) just works. Porting the same expression to Java, C++, or Go with 32-bit arithmetic silently overflows: with k up to 10⁹-scale and element differences up to 10⁹-scale, the product can far exceed 2³¹ - 1.

// Buggy Java port — overflows for large inputs:
int answer = k * (maxValue - minValue);

The solution: Promote to a 64-bit type before the multiplication, not after:

long answer = (long) k * (maxValue - minValue);

long long answer = (long long) k * (maxValue - minValue);

Casting the result after multiplying ((long)(k * diff)) does not help — the overflow has already happened in 32-bit arithmetic.

4. Subtle bug in the single-pass min/max variant

The pitfall: When tracking both extremes in one loop, a common template initializes with sentinel values or starts the loop at the wrong index:

max_value, min_value = 0, 0          # Wrong: breaks for all-negative or all-positive arrays
for num in nums:
    if num > max_value:
        max_value = num
    elif num < min_value:
        min_value = num

For nums = [-5, -2, -9], this returns 0 - (-9) = 9 instead of the correct -2 - (-9) = 7.

The solution: Initialize both extremes to an actual array element (nums[0]), which is always safe since subarrays are non-empty:

max_value = min_value = nums[0]
for num in nums:
    if num > max_value:
        max_value = num
    elif num < min_value:
        min_value = num
return k * (max_value - min_value)

Note that the elif is safe only because both variables start at nums[0]; with sentinel initialization, the elif could skip a necessary min-update on the very element that should set both extremes.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: