Range Sum of Sorted Subarray Sums

Given the array nums consisting of n positive integers. You computed the sum of all non-empty continuous subarrays from the array and then sort them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers.
Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 10^9 + 7.

Example 1:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
Output: 13 

Approach

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class RangeSumSortedSubarray {
    public static void main(String[] args) {
        int[] nums = { 1, 2, 3, 4 };
        int n = 4, left = 1, right = 5;
        System.out.println(rangeSum(nums, n, left, right));
    }
    static int MOD = 1000000007;
    static int rangeSum(int[] nums, int n, int left, int right) {
        List<Integer> v = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                v.add(sum);
            }
        }
        Collections.sort(v);
        int ans[] = new int[v.size() + 1];
        ans[1] = v.get(0);
        for (int i = 1; i < v.size(); i++)
            ans[i + 1] = (v.get(i) + ans[i]) % MOD;
        return ans[right] - ans[left - 1];
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
long long int rangeSum(vector<int> &nums, int n, int left, int right)
{
    vector<int> v;
    for (int i = 0; i < n; i++)
    {
        long long int sum = 0;
        for (int j = i; j < n; j++)
        {
            sum += nums[j];
            v.push_back(sum);
        }
    }
    sort(v.begin(), v.end());
    long long int ans[v.size() + 1];
    memset(ans, 0, sizeof(ans));
    ans[1] = v[0];
    for (int i = 1; i < v.size(); i++)
        ans[i + 1] = (v[i] + ans[i]) % MOD;
    return ans[right] - ans[left - 1];
}
int main()
{
    vector<int> nums = {1, 2, 3, 4};
    int n = 4, left = 1, right = 5;
    cout << rangeSum(nums, n, left, right);
    return 0;
}