Maximum Total Subarray Value I

medium array greedy subarray

Problem

Given an integer array nums and an integer k, choose exactly k non-empty subarrays nums[l..r]. Subarrays may overlap and the same subarray may be picked more than once. The value of a subarray is max(nums[l..r]) − min(nums[l..r]), and the total value is the sum of the chosen subarrays' values. Return the maximum possible total value.

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

Output4

The whole array [1,3,2] has value 3 − 1 = 2. Picking it twice gives 2 + 2 = 4.

nums (comma-separated)

def maxTotalValue(nums, k):
    # The value of any subarray is max - min. Among all subarrays,
    # the whole array gives the largest possible max - min, because
    # adding more elements can only raise the max or lower the min.
    hi = max(nums)            # global maximum
    lo = min(nums)            # global minimum
    # We may reuse the same subarray, so pick the whole array k times.
    return (hi - lo) * k

function maxTotalValue(nums, k) {
  // The value of any subarray is max - min. The whole array gives the
  // largest possible max - min, so we choose it for all k picks.
  let hi = nums[0], lo = nums[0];
  for (const v of nums) {       // scan once for global max and min
    if (v > hi) hi = v;
    if (v < lo) lo = v;
  }
  // BigInt guards the long return type (up to 1e9 * 1e5).
  return Number(BigInt(hi - lo) * BigInt(k));
}

long maxTotalValue(int[] nums, int k) {
    // The value of any subarray is max - min. The whole array gives the
    // largest possible max - min, so we choose it for all k picks.
    int hi = nums[0], lo = nums[0];
    for (int v : nums) {          // scan once for global max and min
        if (v > hi) hi = v;
        if (v < lo) lo = v;
    }
    // Cast to long: (max - min) * k can exceed 32-bit range.
    return (long) (hi - lo) * k;
}

long long maxTotalValue(vector<int>& nums, int k) {
    // The value of any subarray is max - min. The whole array gives the
    // largest possible max - min, so we choose it for all k picks.
    int hi = nums[0], lo = nums[0];
    for (int v : nums) {          // scan once for global max and min
        if (v > hi) hi = v;
        if (v < lo) lo = v;
    }
    // Cast to long long: (max - min) * k can exceed 32-bit range.
    return (long long)(hi - lo) * k;
}

Explanation

The key observation is that the value of a subarray only ever grows as you widen it. If you start from any window and extend it left or right, the new element either raises the maximum, lowers the minimum, or changes neither — it can never shrink max − min. So the single subarray with the greatest value is always the entire array.

Because the problem lets us reuse the same subarray as many times as we like, there is no reason to ever pick a smaller, lower-value window. The optimal strategy is to choose the whole array all k times. Every pick then contributes the same maximal value (global max − global min).

That collapses the whole problem to a one-line formula: scan once to find the global maximum hi and global minimum lo, then return (hi − lo) · k. No actual subarray enumeration is needed.

One detail matters: the result can be as large as 10⁹ · 10⁵ = 10¹⁴, which overflows a 32-bit integer. The return type is a 64-bit long, so we widen the multiplication accordingly (a long cast in Java/C++, BigInt in JavaScript).

Example: nums = [1, 3, 2], k = 2. The global max is 3 and the global min is 1, so each pick is worth 2, and two picks give 2 · 2 = 4.

Time: O(n) Space: O(1)