403669: GYM101237 F Just Another Sequence Problem

You are given a sequence (A₁, A₂, ..., A_N) consisting of integers. Your task is to split this sequence into contiguous non-empty parts such that the value S₁·S₂ + S₂·S₃ + ... + S_k - 1·S_k is as large as possible, where k is the total number of parts and S_i is the sum of all integers in i-th part (in the order from left to right).

Note that if k = 1, this value is assumed to be equal to zero.

The first line contains the integer N, the length of the sequence (1 ≤ N ≤ 2000).

The second line contains integers A₁, A₂, ..., A_N separated by spaces ( - 1000 ≤ A_i ≤ 1000).

Output the maximal possible value of S₁·S₂ + S₂·S₃ + ... + S_k - 1·S_k.

6
2 -1 4 3 -1 0

13

In the example case, the optimal partition is (2,  - 1), (4), (3), ( - 1, 0), it produces the value S₁·S₂ + S₂·S₃ + S₃·S₄ = 1·4 + 4·3 + 3·( - 1) = 13.