P7421 "PMOI-2" Subsequence

When you see this time limit, there is no need to panic. This problem does not rely on constant-factor tricks.

You are given a sequence $a_i$ of length $n$ (**indices start from $1$**). You need to choose a non-empty subsequence $p$ of $\{1,2,3,\cdots,n\}$ with any length. Let the length of $p$ be $l$. Define $a_0=p(0)=a_{n+1}=0,p(l+1)=n+1$. You need to maximize: $$\sum_{i=0}^{l}(a_{p(i+1)}-a_{p(i)})(p(l-i+1)-p(l-i))$$ Output the maximum value. If $a$ is a subsequence of $b$, then $a$ can be obtained by deleting zero or more elements from $b$ **while keeping the original order**. For example, $\{1,4\}$ is a subsequence of $\{1,2,3,4\}$, $\{3,1,5\}$ is a subsequence of $\{3,1,5\}$, and $\{1,2\}$ is not a subsequence of $\{3,2,1\}$.

The first line contains a positive integer $n$, representing the length of $a$. The second line contains $n$ integers, where the $i$-th number is $a_i$.

Output one integer, representing the maximum value of $\sum_{i=0}^{l}(a_{p(i+1)}-a_{p(i)})(p(l-i+1)-p(l-i))$.

[Sample Explanation] For the first sample, choosing $\{1\}$ gives the maximum result $(1-0)\times(4-1)+(0-1)\times(1-0)=2$. For the second sample, choosing $\{1,5\}$ gives the maximum result $(-2-0)\times(6-5)+[3-(-2)]\times(5-1)+(0-3)\times(1-0)=15$. [Constraints] For $20\%$ of the testdata, $n\le20$ and $0\le a_i\le10^3$. For $50\%$ of the testdata, $n\le80$. For $100\%$ of the testdata, $1\le n\le300$ and $-10^9\le a_i\le10^9$. Translated by ChatGPT 5