Maximum total subarray value i

Array Greedy

64.3% acceptance

Feb 25, 2026

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] of nums. Subarrays may overlap, and the exact same subarray (same l and r) can be chosen more than once. The value of a subarray nums[l..r] is defined as: max(nums[l..r]) - min(nums[l..r]). The total value is the sum of the values of all chosen subarrays. Return the maximum possible total value you can achieve.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_total_value(nums: Vec<i32>, k: i32) -> i64 {
    // Best single subarray value = max(nums) - min(nums) (full array or any subarray containing both extremes).
    // Pick the best subarray k times.
    let max_val = *nums.iter().max().unwrap() as i64;
    let min_val = *nums.iter().min().unwrap() as i64;
    (max_val - min_val) * k as i64
  }
}