Little Girl and Maximum Sum Problem

Little Girl and Maximum Sum Problem — ExecCode Medium DSA Practice

Solve the Little Girl and Maximum Sum problem on ExecCode. Free online medium DSA practice in Two Pointers. Write and run code in Java, C++, Python — no signup required to run.

Problem description

You may rearrange an array once. After that, each query adds the sum of a 1-based inclusive segment to the score. Return the maximum possible total score. Use a 64-bit integer. You are given: a — the values, which may be rearranged queries — 1-based inclusive segments [left, right] Return the maximum total of all segment sums, as a 64-bit integer. A position that lies in more queries should receive a larger value. Count the queries covering each index with a difference array, then pair the largest values with the largest counts.

Examples

Input {'a': [5, 3, 2], 'queries': [[1, 2], [2, 3], [1, 3]]}; Output 25. Input {'a': [1, 2], 'queries': [[1, 1]]}; Output 2. Input {'a': [4, 1, 3], 'queries': [[1, 3]]}; Output 8

Constraints

1 <= a.length <= 100000 1 <= queries.length <= 100000 1 <= left <= right <= a.length 0 <= a[i] <= 1000000000 The answer fits in a signed 64-bit integer

Practice Little Girl and Maximum Sum free on ExecCode. Browse DSA problems, topic map, and placement guides.