What is the key pattern in Maximum Sum Obtained of Any Permutation?

The key pattern is greedy choice guided by index frequency counting, pairing largest numbers with the most requested indices.

Why do we use prefix sums in this problem?

Prefix sums efficiently calculate how many times each index is requested across overlapping intervals, avoiding nested loops.

Can nums contain zeros or large numbers?

Yes, nums elements can be zero or up to 10^5, which is why sorting and modular arithmetic are necessary.

Is sorting both nums and frequency array required?

Yes, sorting ensures the largest numbers are assigned to the most frequently requested indices for maximum total sum.

How does GhostInterview handle large outputs?

It applies modulo 10^9+7 automatically and highlights the correct greedy pairing to prevent overflow while maximizing sum.

#1589

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

所有排列中的最大和

有一个整数数组 nums ，和一个查询数组 requests ，其中 requests[i] = [start i , end i ] 。第 i 个查询求 nums[start i ] + nums[start i + 1] + ... + nums[end i - 1] + nums[end i …

数组贪心排序前缀和

题目描述

有一个整数数组 nums ，和一个查询数组 requests ，其中 requests[i] = [start_i, end_i] 。第 i 个查询求 nums[start_i] + nums[start_i + 1] + ... + nums[end_i - 1] + nums[end_i] 的结果，start_i 和 end_i 数组索引都是 从 0 开始 的。

你可以任意排列 nums 中的数字，请你返回所有查询结果之和的最大值。

由于答案可能会很大，请你将它对 10⁹ + 7 取余后返回。

示例 1：

输入：nums = [1,2,3,4,5], requests = [[1,3],[0,1]]
输出：19
解释：一个可行的 nums 排列为 [2,1,3,4,5]，并有如下结果：
requests[0] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8
requests[1] -> nums[0] + nums[1] = 2 + 1 = 3
总和为：8 + 3 = 11。
一个总和更大的排列为 [3,5,4,2,1]，并有如下结果：
requests[0] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11
requests[1] -> nums[0] + nums[1] = 3 + 5  = 8
总和为： 11 + 8 = 19，这个方案是所有排列中查询之和最大的结果。

示例 2：

输入：nums = [1,2,3,4,5,6], requests = [[0,1]]
输出：11
解释：一个总和最大的排列为 [6,5,4,3,2,1] ，查询和为 [11]。

示例 3：

输入：nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]]
输出：47
解释：一个和最大的排列为 [4,10,5,3,2,1] ，查询结果分别为 [19,18,10]。

提示：

n == nums.length
1 <= n <= 10⁵
0 <= nums[i] <= 10⁵
1 <= requests.length <= 10⁵
requests[i].length == 2
0 <= start_i <= end_i < n

lightbulb

解题思路

方法一：差分数组 + 排序 + 贪心

我们观察发现，对于一次查询操作，会返回该查询区间 $[l, r]$ 中的所有元素之和。而题目要求的是所有查询操作的结果之和的最大值，也即是说，我们要累计所有查询操作的结果，使得这些结果之和最大。因此，如果一个下标 $i$ 在查询操作中出现的次数越多，那么我们就应该赋给下标 $i$ 一个较大的值，这样才能使得所有查询操作的结果之和最大。

因此，我们可以用差分数组的思想，统计每个下标在查询操作中出现的次数，然后对这些次数从小到大进行排序，然后对数组 $\textit{nums}$ 也从小到大进行排序，这样就能保证每个下标 $i$ 在查询操作中出现的次数越多，该下标对应的值 $\textit{nums}[i]$ 就越大。接下来，我们只需要将这些下标对应的值 $\textit{nums}[i]$ 与其在查询操作中出现的次数相乘，然后累加起来，就是所有查询操作的结果之和的最大值。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

speed

复杂度分析

指标	值
时间	complexity is O(n + m + n log n) where n is the length of nums and m is the number of requests due to prefix sum computation and sorting. Space complexity is O(n) for the frequency array.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Recognizes index frequency counting as critical for greedy maximization
question_mark
Considers sorting both nums and frequency array for optimal assignment
question_mark
Ensures modular arithmetic is applied for large sums

warning

常见陷阱

外企场景

error
Ignoring prefix sum optimization and using nested loops over requests
error
Assigning numbers without sorting by frequency leading to suboptimal sums
error
Forgetting to apply modulo 10^9+7 causing overflow

swap_horiz

进阶变体

外企场景

arrow_right_alt
Minimize sum instead of maximize using similar frequency logic
arrow_right_alt
Requests may overlap non-contiguously, testing frequency accumulation
arrow_right_alt
Allow negative numbers in nums requiring careful pairing

help

常见问题

外企场景

继续练习

#1838 最高频元素的频数 #2171 拿出最少数目的魔法豆 #2234 花园的最大总美丽值