Editorial for Singularity Cup P1 - Maximum Permutation Product

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Mystical

Subtask 1

We can compute the value of every possible subarray and determine which one yields the highest value.

Time complexity: \mathcal{O}(N^2)

Subtask 2

When N \ge 4, it is always optimal to include the entire array excluding 1 if A_1 = 1 or A_N = 1.

N = 3 is an edge case where choosing the subarray that only contains the element 3 is always optimal.

Time complexity: \mathcal{O}(N)


There are no comments at the moment.