CODECHEF: JUNE CHALLENGE | MATHBUZZ | PYTHON, JAVA, C++ SOLUTION

Codechef

View problem on codechef

Akash has just learned the maximum subarray sum problem. And while thinking about the solution, he came up with a new problem, the maximum frequent subarray sum problem.

In this problem, you will be given an array AA of NN integers. You have to choose a non-empty subarray with the maximum possible score. The score of a subarray is calculated asscore(l,r)=(Al+⋯+Ar)⋅(occurrences)score(l,r)=(Al+⋯+Ar)⋅(occurrences)Here, occurrencesoccurrences is the number of occurrences of that subarray in AA.

Now Akash can’t solve this problem, so please help him solve it.

Input

- The first line contains an integer TT, the number of test cases. Then the test cases follow.

- The first line of each test case contains an integer nn, the size of the array.

- The second line contains nn integers A1,…,ANA1,…,AN.

Output

For each test case, output the maximum possible score in a new line.

Constraints

- 1≤T≤2⋅1051≤T≤2⋅105

- 1≤n≤1051≤n≤105

- −107≤Ai≤107−107≤Ai≤107

- The sum of nn over all test cases ≤3⋅105≤3⋅105

Subtasks

- Subtask 1 (10 points): 1≤n≤1001≤n≤100, the sum of nn over all test cases ≤300≤300

- Subtask 2 (15 points): 1≤n≤10001≤n≤1000, the sum of nn over all test cases ≤3000≤3000

- Subtask 3 (75 points): original constraints

Sample Input

2

6

10 8 -20 5 5 5

10

-5 1 7 -1 2 -4 10 0 -11 3

Sample Output

20

15

Explanation

In the first test case, the maximum score is attained by subarray , its score is (5+5)⋅2=20(5+5)⋅2=20 since it occurs twice in AA.

In the second test case, the maximum score is attained by both subarrays and . Both have sum 1515 and occur once, so their scores are 15⋅1=1515⋅1=15.

SOLUTION

Read more post Here