# Maximum Sum Obtained of Any Permutation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-sum-obtained-of-any-permutation)
Canonical: https://scaleengineer.com/dsa/problems/maximum-sum-obtained-of-any-permutation
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [PayPal](https://scaleengineer.com/companies/paypal)
---
## Problem
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`

# Approaches
## Brute-force Frequency Calculation
This approach directly simulates the process of counting how many times each index is requested. It iterates through each request and, for each request, iterates through all the indices it covers, incrementing a counter for each index. This count array represents the "importance" of each index. To maximize the total sum, we pair the largest numbers from `nums` with the indices that are requested most frequently.
**Time:** O(m * n + n log n), where `n` is the length of `nums` and `m` is the number of requests. The `O(m * n)` part comes from iterating through all requests and updating frequencies. `O(n log n)` is for sorting. Given the constraints, this is too slow. · **Space:** O(n) to store the frequency array.
**Pros:** Simple to understand and implement.; Correctly identifies the core greedy strategy of pairing large numbers with high-frequency indices.
**Cons:** The frequency calculation step is very slow.; Time complexity is dominated by the nested loops, making it infeasible for large inputs. It will result in a "Time Limit Exceeded" (TLE) error on competitive programming platforms.
### Explanation
The core idea is that to maximize the sum `Σ(count[i] * nums_permuted[i])`, we must assign the largest values from `nums` to the indices `i` with the highest `count[i]`. 

First, we need to determine the frequency `count[i]` for each index `i`, which is the number of requests that include this index. We can create a frequency array, `freq`, of the same size as `nums`. We iterate through every request `[start, end]`. For each request, we loop from `start` to `end` and increment `freq[j]` for each index `j` in this range. 

After calculating all frequencies, we sort both the `nums` array and the `freq` array in non-decreasing order. The maximum total sum is then the sum of the products of the corresponding elements from the sorted arrays: `sum(sorted_nums[i] * sorted_freq[i])`. Since the result can be large, we perform the summation modulo `10^9 + 7`.

```java
import java.util.Arrays;

class Solution {
    public int maxSumRangeQuery(int[] nums, int[][] requests) {
        int n = nums.length;
        int[] freq = new int[n];
        
        // Step 1: Calculate frequency for each index (Brute-force)
        for (int[] req : requests) {
            int start = req[0];
            int end = req[1];
            for (int i = start; i <= end; i++) {
                freq[i]++;
            }
        }
        
        // Step 2: Sort both nums and freq arrays
        Arrays.sort(nums);
        Arrays.sort(freq);
        
        // Step 3: Calculate the maximum total sum
        long totalSum = 0;
        int mod = 1_000_000_007;
        
        for (int i = 0; i < n; i++) {
            totalSum = (totalSum + (long)nums[i] * freq[i]) % mod;
        }
        
        return (int)totalSum;
    }
}
```
### Algorithm
- Create an integer array `freq` of size `n` (length of `nums`), initialized to all zeros.
- Iterate through each `request` in the `requests` array.
- For each `request = [start, end]`, iterate from `i = start` to `end` and increment `freq[i]`.
- Sort the `nums` array in ascending order.
- Sort the `freq` array in ascending order.
- Initialize a variable `maxSum` to 0.
- Iterate from `i = 0` to `n-1`. In each iteration, add the product of `nums[i]` and `freq[i]` to `maxSum`. Apply modulo `10^9 + 7` at each addition to prevent overflow.
- Return `maxSum`.

## Optimized Frequency Calculation using Difference Array
This approach improves upon the brute-force method by calculating the index frequencies more efficiently. Instead of iterating through each range for every request, it uses a technique similar to a difference array or a line sweep algorithm. This reduces the time to calculate all frequencies from `O(m * n)` to `O(n + m)`. The rest of the logic, which involves sorting and pairing, remains the same.
**Time:** O(m + n + n log n). `O(m + n)` for frequency calculation (processing requests and computing prefix sums). `O(n log n)` for sorting both arrays. The overall complexity is dominated by sorting for large `n`. · **Space:** O(n) to store the frequency array.
**Pros:** Highly efficient frequency calculation.; The overall time complexity is dominated by sorting, which is much better than the brute-force approach.; This solution is efficient enough to pass within the given constraints.
**Cons:** The difference array technique might be slightly less intuitive for beginners compared to the direct simulation.
### Explanation
The bottleneck in the previous approach is calculating the frequency array. We can optimize this part significantly. The problem of adding 1 to all elements in multiple ranges `[start, end]` can be solved efficiently. We can create an array, let's call it `freq`, of size `n`.

For each request `[start, end]`, we increment `freq[start]` by 1 and, if `end + 1` is within bounds, we decrement `freq[end + 1]` by 1. The `freq[i]` now represents the net change in frequency count at index `i`.

After processing all requests, we can compute the actual frequency for each index by taking the prefix sum of this array. That is, `freq[i] = freq[i-1] + freq[i]` (after the initial marking phase). This process computes the frequency array in `O(n + m)` time.

Once the `freq` array is computed, the rest of the algorithm is identical to the first approach: sort `nums` and `freq`, then compute the dot product.

```java
import java.util.Arrays;

class Solution {
    public int maxSumRangeQuery(int[] nums, int[][] requests) {
        int n = nums.length;
        int[] freq = new int[n];
        
        // Step 1: Efficiently calculate frequency using difference array concept
        for (int[] req : requests) {
            freq[req[0]]++;
            if (req[1] + 1 < n) {
                freq[req[1] + 1]--;
            }
        }
        
        // Step 2: Compute prefix sums to get the actual frequencies
        for (int i = 1; i < n; i++) {
            freq[i] += freq[i - 1];
        }
        
        // Step 3: Sort both nums and freq arrays
        Arrays.sort(nums);
        Arrays.sort(freq);
        
        // Step 4: Calculate the maximum total sum
        long totalSum = 0;
        int mod = 1_000_000_007;
        
        for (int i = 0; i < n; i++) {
            totalSum = (totalSum + (long)nums[i] * freq[i]) % mod;
        }
        
        return (int)totalSum;
    }
}
```
### Algorithm
- Create an integer array `freq` of size `n`, initialized to all zeros. This array will first be used as a difference array.
- Iterate through each `request = [start, end]` in `requests`.
- For each request, increment `freq[start]` by 1.
- If `end + 1 < n`, decrement `freq[end + 1]` by 1.
- After processing all requests, convert the difference array into the actual frequency array by computing its prefix sum. Iterate from `i = 1` to `n-1` and update `freq[i] = freq[i] + freq[i-1]`.
- Sort the `nums` array in ascending order.
- Sort the `freq` array in ascending order.
- Initialize a variable `maxSum` to 0.
- Iterate from `i = 0` to `n-1`, adding the product of `nums[i]` and `freq[i]` to `maxSum`. Apply modulo `10^9 + 7` at each step.
- Return `maxSum`.

# Solutions
### Java

```java
class Solution {
public
  int maxSumRangeQuery(int[] nums, int[][] requests) {
    int n = nums.length;
    int[] d = new int[n];
    for (var req : requests) {
      int l = req[0], r = req[1];
      d[l]++;
      if (r + 1 < n) {
        d[r + 1]--;
      }
    }
    for (int i = 1; i < n; ++i) {
      d[i] += d[i - 1];
    }
    Arrays.sort(nums);
    Arrays.sort(d);
    final int mod = (int)1 e9 + 7;
    long ans = 0;
    for (int i = 0; i < n; ++i) {
      ans = (ans + 1L * nums[i] * d[i]) % mod;
    }
    return (int)ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxSumRangeQuery(vector<int> &nums, vector<vector<int>> &requests) {
    int n = nums.size();
    int d[n];
    memset(d, 0, sizeof(d));
    for (auto &req : requests) {
      int l = req[0], r = req[1];
      d[l]++;
      if (r + 1 < n) {
        d[r + 1]--;
      }
    }
    for (int i = 1; i < n; ++i) {
      d[i] += d[i - 1];
    }
    sort(nums.begin(), nums.end());
    sort(d, d + n);
    long long ans = 0;
    const int mod = 1e9 + 7;
    for (int i = 0; i < n; ++i) {
      ans = (ans + 1LL * nums[i] * d[i]) % mod;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int: n = len(nums) d = [0] * n for l, r in requests: d[l] += 1 if r + 1 < n: d[r + 1] -= 1 for i in range(1, n): d[i] += d[i - 1] nums . sort() d . sort() mod = 10 ** 9 + 7 return sum(a * b for a, b in zip(nums, d)) % mod

```