CF1872G Replace With Product

Given an array $ a $ of $ n $ positive integers. You need to perform the following operation exactly once: - Choose $ 2 $ integers $ l $ and $ r $ ( $ 1 \le l \le r \le n $ ) and replace the subarray $ a[l \ldots r] $ with the single element: the product of all elements in the subarray $ (a_l \cdot \ldots \cdot a_r) $ . For example, if an operation with parameters $ l = 2, r = 4 $ is applied to the array $ [5, 4, 3, 2, 1] $ , the array will turn into $ [5, 24, 1] $ . Your task is to maximize the sum of the array after applying this operation. Find the optimal subarray to apply this operation.

N/A

N/A

In the first test case, after applying the operation with parameters $ l = 2, r = 4 $ , the array $ [1, 3, 1, 3] $ turns into $ [1, 9] $ , with a sum equal to $ 10 $ . It is easy to see that by replacing any other segment with a product, the sum will be less than $ 10 $ . In the second test case, after applying the operation with parameters $ l = 3, r = 4 $ , the array $ [1, 1, 2, 3] $ turns into $ [1, 1, 6] $ , with a sum equal to $ 8 $ . It is easy to see that by replacing any other segment with a product, the sum will be less than $ 8 $ . In the third test case, it will be optimal to choose any operation with $ l = r $ , then the sum of the array will remain $ 5 $ , and when applying any other operation, the sum of the array will decrease.