[초등부] 2024 KOI 2차대회 대비 모의고사 (2주차)

수열 A는 N개의 정수들로 이루어져 있다.

수열 A를 네 구간으로 나누려고 한다. (하나의 구간에는 반드시 연속된 원소만이 존재한다)

예를 들어 A=[2,4,1,3,5]이라면, [2],[4],[1],[3,5]와 같이 나누거나 [2],[4,1],[3],[5]와 같이 나누는 등 다양한 방법이 가능하다.

구간을 나누는 비용은 각 구간의 곱의 합으로 결정된다.

하나의 구간이 i에서 j까지라면, 해당 구간의 곱은 A_i × A_{i+1} × ... × A_{j-1} × A_j (i ≤ j)으로 결정되고, 각 네 구간의 곱의 합이 최종적인 비용이 된다.

비용의 최댓값과 최솟값을 구하는 프로그램을 작성하시오.