Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Train Hijack

By cosmicray001 · Limits 1s, 512 MB

You and your friend Daneliya Tuleshova are planning to hijack a train. Your friend will go inside a cabin and she will throw valuable things through the windows. Your task is to collect it. But there are lots of things inside the cabin so she is throwing whatever she finds. There are different kinds of things in the cabin and they have different values in the market. However, you can't just only pick valuable things. You must collect items consecutively so that the product of their market values becomes maximum. There can't be any unpicked item between any two picked items.


Input starts with a single integer T (1 ≤ T ≤ 100000) denoting the number of test cases. For every test case, there will be a positive integer N (1 ≤ N ≤ 60) denoting the number of things are thrown by Daneliya Tuleshova. Next line there will be N numbers a (-2 ≤ a1, a2, a3, ..........., aN ≤ 2) denotes the value of the things.


Print the case number and the maximum contiguous subarray product. See the format in the sample test case.


-2 -2 -1 0 2
Case 1: 4



70% Solution Ratio

RamprosadGEarliest, Dec '19

prodip_bsmrstuFastest, 0.2s

siam009Lightest, 3.2 MB

theunownShortest, 439B


Login to submit

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.