{x}
blog image

Maximum Sum Obtained of Any Permutation

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[starti + 1] + ... + nums[endi - 1] + nums[endi]. Both starti and endi are 0-indexed.

Return the maximum total sum of all requests among all permutations of nums.

Since the answer may be too large, return it modulo 109 + 7.

 

Example 1:

Input: nums = [1,2,3,4,5], requests = [[1,3],[0,1]]
Output: 19
Explanation: One permutation of nums is [2,1,3,4,5] with the following result: 
requests[0] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8
requests[1] -> nums[0] + nums[1] = 2 + 1 = 3
Total sum: 8 + 3 = 11.
A permutation with a higher total sum is [3,5,4,2,1] with the following result:
requests[0] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11
requests[1] -> nums[0] + nums[1] = 3 + 5  = 8
Total sum: 11 + 8 = 19, which is the best that you can do.

Example 2:

Input: nums = [1,2,3,4,5,6], requests = [[0,1]]
Output: 11
Explanation: A permutation with the max total sum is [6,5,4,3,2,1] with request sums [11].

Example 3:

Input: nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]]
Output: 47
Explanation: A permutation with the max total sum is [4,10,5,3,2,1] with request sums [19,18,10].

 

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • 0 <= nums[i] <= 105
  • 1 <= requests.length <= 105
  • requests[i].length == 2
  • 0 <= starti <= endi < n

Solution Explanation: Maximum Sum Obtained of Any Permutation

This problem asks to find the maximum total sum of all requests among all permutations of nums, where each request is a range sum within nums. The solution leverages the concept of a difference array and greedy approach for optimization.

1. Difference Array:

The core idea is to efficiently count how many times each index of nums is included in the requests. Instead of iterating through each request and summing up elements, we use a difference array d. d[i] will store the net increase in the count of times index i is included in the ranges specified by the requests.

  • Initialization: d is initialized to all zeros.
  • Increment and Decrement: For each request [start, end], we increment d[start] by 1 (because index start is included) and decrement d[end + 1] by 1 (this is a clever technique to handle the inclusive range). The decrement at end+1 will correctly account for the range sum when we compute the prefix sum of d.
  • Prefix Sum: A prefix sum calculation transforms d into an array where d[i] now represents the total number of times index i is included across all requests.

2. Greedy Approach and Sorting:

Once we have the count of appearances (d), the greedy strategy becomes clear: To maximize the total sum, we want to assign the largest values in nums to indices that appear most frequently in the requests.

  • Sort: Both nums and d are sorted in ascending order. This ensures that the largest elements in nums are paired with the indices with the highest counts in d.
  • Calculate Sum: The final sum is calculated by multiplying corresponding elements from the sorted nums and d arrays. This process efficiently computes the maximum possible total sum of all requests.

3. Complexity Analysis:

  • Time Complexity: O(n log n), dominated by the sorting of nums and d arrays. The other operations (difference array creation, prefix sum, and final sum calculation) are all linear O(n).
  • Space Complexity: O(n), to store the difference array d.

Code Examples (Python):

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        d = [0] * n  # Initialize difference array
        for start, end in requests:
            d[start] += 1
            if end + 1 < n:
                d[end + 1] -= 1  # Decrement to handle inclusive range
 
        for i in range(1, n):
            d[i] += d[i - 1]  # Calculate prefix sum
 
        nums.sort()
        d.sort()
 
        mod = 10**9 + 7
        total_sum = 0
        for i in range(n):
            total_sum = (total_sum + nums[i] * d[i]) % mod
 
        return total_sum

This Python code directly implements the steps described above. Other languages (Java, C++, Go, TypeScript) would follow a very similar structure, adapting the syntax and data structures appropriately (as shown in the original response). The core algorithmic approach remains the same across all implementations.