Long has an array $$$a$$$ consisting of $$$n$$$ elements $$$a_1,a_2,...,a_n$$$. Help Long find the maximum value of $$$P=\left(\sum_{k=i}^j a_k\right)^2-\sum_{k=i}^j a_k^2$$$ with $$$1\leq i\leq j\leq n$$$.
Input:
The first line contains an integer $$$n \left(3\leq n \leq5.10^5\right)$$$.
The second line contains $$$n$$$ space-separated integers $$$a_1,a_2,...,a_n \left(-10^3\leq a_i \leq10^3\right)$$$.
Output:
The maximum value of $$$P$$$.
I have an idea to use dp but haven't built a formula yet
There are some testcases: Test 1: Input: 4 5 4 -6 4 Output: 40
Test 2: Input: 7 -7 8 -1 5 4 -6 4 Output: 150
I think it uses Kadane's DP, but you have to keep track of the optimal range throughout the process.
thanks for the solution
I submitted this code. Result is wrong answer
Define two prefix sum arrays $$$p_i = \sum_{1}^{i} a_i$$$ and $$$q_i = \sum_{1}^{i} a_i^2$$$ then for interval $$$(l, r]$$$ we have
rewrite this to get
Now fix $$$r$$$. You want to get the optimal $$$l$$$ for equation above. First notice that $$$(p_r^2 - q_r)$$$ does not depend on $$$l$$$. Then notice that the remaining parts are of the form $$$P = a_l(p_r) + b_l$$$. So you can sweep over $$$r$$$ and use convex hull trick to get the maximum $$$P$$$.
thanks for the solution
send the problem link or otherwise how do we know you arent cheating from some online contest