Page Contents

*Maximum Frequent Subarray Sum MFSS*

*Maximum Frequent Subarray Sum MFSS*

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 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 Akash can’t solve this problem, so please help him solve it.

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.

Constraints

1≤T≤2⋅105

1≤n≤105

−107≤Ai≤107

The sum of n over all test cases ≤3⋅105

Subtasks

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

Subtask 2 (15 points): 1≤n≤1000, the sum of n over all test cases ≤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 [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.

*Program:*

```
def solve():
n = int(input())
arr = list(map(int,input().split()))
freq, ans = {},-1000000009
for i in range(n):
for j in range(i,n):
item = tuple(arr[i:j+1])
if item in freq.keys():
freq[item]+=1
else:
freq[item]=1
for key, val in freq.items():
pts = sum(key)*val
# print()
if pts>=ans:
ans = pts
print(ans)
def main():
t = int(input())
for i in range(t):
solve()
main()
```

*June Long Challenge 2021 Solutions*

*June Long Challenge 2021 Solutions*

*Maximum Frequent Subarray Sum solution codechef**Dual Distance solution codechef**Optimal Xor Set solution codechef**Minimum Subtree Cover solution codechef**Minimum Dual Area solution codechef**Bitwise Tuples solution codechef**Shortest Route solution codechef**Bella ciao solution codechef**Summer Heat solution codechef*

*March Long Challenge 2021 Solutions*

*March Long Challenge 2021 Solutions*