所有排列中的最大和

标签: 贪心 数组 前缀和 排序

难度: Medium

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

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

由于答案可能会很大，请你将它对 109 + 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 <= 105
  • 0 <= nums[i] <= 105
  • 1 <= requests.length <= 105
  • requests[i].length == 2
  • 0 <= starti <= endi < n

Submission

运行时间: 148 ms

内存: 43.0 MB

MOD = 10 ** 9 + 7

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        # 差分数组
        diff = [0] * (len(nums) + 1)
        for l, r in requests:
            diff[l] += 1
            diff[r + 1] -= 1
        diff.pop()

        times = sorted(filter(None, accumulate(diff)), reverse=True)
        nums.sort(reverse=True)
        return sum(map(mul, times, nums)) % MOD

Explain

The solution utilizes a difference array to efficiently calculate the frequency of each index being accessed across all requests. First, it iterates through each request and updates the difference array to track the start and end+1 of each range. Then, by taking the prefix sum of this difference array, we get the number of times each index is accessed. After sorting this 'times' array and the 'nums' array in descending order, the product of corresponding elements from both arrays (the highest numbers with the highest frequencies) maximizes the sum. The result is then taken modulo 109 + 7.

时间复杂度: O(n log n + m)

空间复杂度: O(n)

MOD = 10 ** 9 + 7

from itertools import accumulate
from operator import mul

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        # Create a difference array to handle the range update efficiently
        diff = [0] * (len(nums) + 1)
        for l, r in requests:
            diff[l] += 1  # Start of the range
            diff[r + 1] -= 1  # End of the range (exclusive)
        diff.pop()  # Remove the last element which is extra

        # Compute the number of times each index is accessed
        times = sorted(filter(None, accumulate(diff)), reverse=True)
        # Sort nums in descending order to maximize the sum
        nums.sort(reverse=True)
        # Compute the sum of products of corresponding elements
        return sum(map(mul, times, nums)) % MOD

Explore

差分数组是一种用于高效处理区间增减操作的数据结构。在本题中，每个请求定义了一个增加的区间，直接更新整个区间的每个元素将非常耗时，特别是当数组或请求列表很大时。使用差分数组，我们只需要在区间的开始位置增加一个值，在结束位置的下一个索引减去相同的值。这样，只有两个操作即可表示整个区间的更新。后续通过累积求和转换差分数组，就可以得到每个索引被访问的次数，这种方法大大提高了效率。

差分数组中的每个元素代表了从当前位置开始，后续所有元素的增减值。使用`accumulate`函数（累积求和）可以将差分数组转换为原始的频次数组。具体来说，差分数组的每一点的变化通过累加传递到后面的所有点，最终形成了每个索引的实际访问次数。这是将局部修改信息扩展为全局访问频率的关键步骤。

将`nums`和`times`数组都按降序排序的目的是使得最大的数和最高的访问频率相乘，从而实现总和的最大化。具体来说，因为我们想最大化数组元素与其被访问次数的乘积之和，故将最大的元素配对最多的访问次数，可以确保每个乘积项尽可能大，进而使得总和最大。这种配对方式基于贪心算法的思想，是获得最大查询和的有效策略。

取模运算`10^9 + 7`是一种常用的方法来防止整数溢出，并且这个数字是一个大的质数，常用于编程竞赛中避免极大数值的处理问题。在处理大量数据或大数乘法时，结果可能超过常规整数类型的存储范围，通过对一个大质数取余，我们可以保持结果在一个安全的数值范围内，同时也满足某些编程竞赛和算法应用的标准要求。