1589. 所有排列中的最大和-差分数组+快速排序+贪心算法

1589. 所有排列中的最大和-差分数组+快速排序+贪心算法

有一个整数数组 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]。

这一题，博主一开始做的时候并没有想到差分数组，查阅了资料之后 才知道这个工具的妙处，可谓非常棒的一个工具，在我们解决问题时，一定可以有很大的帮助，感兴趣的可以了解一下差分数组在统计区间统计数量统计的作用
那么对于这一题，首先统计每个坐标的的统计次数，然后排序，次数，按照次数最多的一次加数组中的较大值，解题代码如下：

void add_r(int *r,int *a,int numsSize){
    r[a[0]]++;
        if (a[1] + 1 < numsSize) {
            r[a[1] + 1]--;
        }


}




void quick_sort(int *a,int low,int high){
    int l=low,h=high;
    if(low<high){
        int p=a[low];
        while(low<high){
            while(low<high&&a[high]<=p){
                high--;

            }
            a[low]=a[high];
            while(low<high&&a[low]>=p){
                low++;
            }
            a[high]=a[low];
        }
        a[low]=p;
        quick_sort(a,l,low-1);
        quick_sort(a,low+1,h);

    }
}

int cmp(const void* a, const void* b)
 {
     return *(int*)a - *(int*)b;
 }

int maxSumRangeQuery(int* nums, int numsSize, int** requests, int requestsSize, int* requestsColSize){

     int  *r=(int *)malloc(sizeof(int)*numsSize);
    for(int i=0;i<numsSize;i++){
        r[i]=0;
    }
    for(int i=0;i<requestsSize;i++){
        add_r(r,requests[i],numsSize);
    }
    for (int i = 1; i < numsSize; i++) {
        r[i] += r[i - 1];
    }


   
    quick_sort(nums,0,numsSize-1);
     quick_sort(r,0,numsSize-1);
     long long re=0;
     for(int i=0;i<numsSize;i++){
         if(r[i]!=0){
             re=(re+r[i]*(long long)nums[i])%1000000007;

         }
     }
    return re;


}