Unequal Goodness

5

2 votes
Data Structures, Advanced Data Structures, Segment Trees
Problem

You are given an array A of N integers. A subarray from l to r (l<r) is good if A[l]!=A[r].

You have to find the maximum possible sum of elements of a good subarray. If there is no such good subarray then print "Not Possible".

Input Format:

  • The first line contains an integer T, which denotes the number of test cases.
  • The first line of each test case contains N.
  • The second line of each test case contains N space-separated integers, denoting the elements of array A.

Output Format: 

For each test case, print the maximum possible sum of elements of good subarray or print "Not Possible" (without double quotes) if there is no such good subarray.

Constraints:

1T102N2105109A[i]109

Time Limit: 4
Memory Limit: 256
Source Limit:
Explanation

For test case 1: The given array is [2,3,2,4,2], here maximum possible sum of elements of a good subarray is 11, which is from index (1,4).

Editor Image

?