PEC-CSS
Frequent Sums
Mr Chaggan Lal 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 A of N integers. You have to choose a non-empty subarray with the maximum possible score. The score of a subarray is calculated as
score(l,r)=(Al+⋯+Ar)⋅(occurrences)
Here, occurrences is the number of occurrences of that subarray in A.
Now Chaggan can't solve this problem as he is aged, so please help him solve it and in return you will get blessings of Chaggan Lal for a Placement😉
Input
- The first line contains an integer T, the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer n, the size of the array.
- The second line contains n integers A1,…,AN.
Output
- For each test case, output the maximum possible score in a new line.
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 [5,5], its score is (5+5)⋅2=20 since it occurs twice in A.
In the second test case, the maximum score is attained by both subarrays [1,7,−1,2,−4,10] and [1,7,−1,2,−4,10,0]. Both have sum 15 and occur once, so their scores are 15⋅1=15.
Hey @Gauravsharma-20, @HarshDutt17 can the code be written in java language and can you assign me this issue to solve the problem
