We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Sum Obtained of Any Permutation

Difficulty: Medium

Problem Description

We have an array of integers, nums, and an array of requests where requests[i] = [start_i, end_i]. The i-th request asks for the sum of nums[start_i] + nums[start_i + 1] + ... + nums[end_i - 1] + nums[end_i]. Both start_i and end_i 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 10^9 + 7.

Key Insights

  • The problem involves calculating the sum of subarrays based on requests.
  • The maximum sum can be achieved by maximizing the values at the indices specified by the requests.
  • Using a frequency array to count how many times each index is accessed by the requests allows us to determine the optimal arrangement of elements in nums.
  • Sorting both the frequency array and nums helps in efficiently calculating the maximum sum.

Space and Time Complexity

Time Complexity: O(n + m log m), where n is the length of nums and m is the number of requests. Space Complexity: O(n), for storing the frequency array.

Solution

To solve the problem, we can use the following approach:

  1. Create a frequency array to count how many times each index is referenced by the requests.
  2. For each request, increment the start index and decrement the end index + 1 in the frequency array.
  3. Compute the prefix sum on the frequency array to get the actual counts of accesses for each index.
  4. Sort the frequency array and the original nums array in descending order.
  5. Multiply the corresponding elements of the sorted frequency and nums arrays to get the maximum sum, then take the result modulo 10^9 + 7.

Code Solutions

def maxSumRangeQuery(nums, requests):
    MOD = 10**9 + 7
    n = len(nums)
    
    freq = [0] * (n + 1)
    
    # Build the frequency array
    for start, end in requests:
        freq[start] += 1
        if end + 1 < n:
            freq[end + 1] -= 1
            
    # Calculate the prefix sums to get the actual frequency counts
    for i in range(1, n):
        freq[i] += freq[i - 1]

    # We only need the first n elements of freq
    freq = freq[:n]
    
    # Sort nums and freq
    nums.sort(reverse=True)
    freq.sort(reverse=True)
    
    # Calculate the maximum sum
    max_sum = sum(num * count for num, count in zip(nums, freq)) % MOD
    
    return max_sum
← Back to All Questions