Maximum sum obtained of any permutation

Array Greedy Sorting Prefix Sum

40.4% acceptance

Feb 25, 2026

824

We have an array of integers, nums, and an array of requests where requests[i] = [starti, endi]. The ith request asks for the sum of nums[starti] + ... + nums[endi]. Return the maximum total sum of all requests among all permutations of nums, modulo 10^9 + 7.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_sum_range_query(mut nums: Vec<i32>, requests: Vec<Vec<i32>>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = nums.len();
    // Count frequency of each index using difference array
    let mut freq = vec![0i32; n + 1];
    for req in &requests {
      freq[req[0] as usize] += 1;
      if req[1] as usize + 1 < n + 1 {
        freq[req[1] as usize + 1] -= 1;
      }
    }
    // Build prefix sum to get actual frequencies
    for i in 1..n {
      freq[i] += freq[i - 1];
    }
    let mut freq = freq[..n].to_vec();
    nums.sort_unstable();
    freq.sort_unstable();
    // Pair largest nums with largest frequencies
    let mut total: i64 = 0;
    for i in 0..n {
      total += freq[i] as i64 * nums[i] as i64;
    }
    (total % MOD) as i32
  }
}