### 1ST_MATHER's blog

By 1ST_MATHER, history, 4 weeks ago,

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$.

• +1

 » 4 weeks ago, # |   0 I have an idea to use dp but haven't built a formula yet
 » 4 weeks ago, # | ← Rev. 2 →   0 There are some testcases: Test 1: Input: 4 5 4 -6 4 Output: 40Test 2: Input: 7 -7 8 -1 5 4 -6 4 Output: 150
 » 4 weeks ago, # | ← Rev. 2 →   0 I think it uses Kadane's DP, but you have to keep track of the optimal range throughout the process. #include #define int long long #define fi first #define se second using namespace std; const int inf = 1e18; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector a(n + 1); for (int i = 1; i <= n; ++i) { cin >> a[i]; } function positive_prior = [&]() { int ans = -inf, ans_l = 0, ans_r = 0; int cur = -inf, cur_l = 0, cur_r = 0; for (int i = 1; i <= n; ++i) { if (a[i] > cur + a[i]) { cur_l = cur_r = i; cur = a[i]; } else { cur_r = i; cur = cur + a[i]; } if (cur > ans) { ans = cur; ans_l = cur_l; ans_r = cur_r; } } ans *= ans; for (int i = ans_l; i <= ans_r; ++i) { ans -= a[i] * a[i]; } return ans; }; function negative_prior = [&]() { int ans = inf, ans_l = 0, ans_r = 0; int cur = inf, cur_l = 0, cur_r = 0; for (int i = 1; i <= n; ++i) { if (a[i] < cur + a[i]) { cur_l = cur_r = i; cur = a[i]; } else { cur_r = i; cur = cur + a[i]; } if (cur < ans) { ans = cur; ans_l = cur_l; ans_r = cur_r; } } ans *= ans; for (int i = ans_l; i <= ans_r; ++i) { ans -= a[i] * a[i]; } return ans; }; cout << max(positive_prior(), negative_prior()) << '\n'; return 0; } 
•  » » 4 weeks ago, # ^ |   0 thanks for the solution
•  » » 4 weeks ago, # ^ |   0 I submitted this code. Result is wrong answer
 » 4 weeks ago, # |   0 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 $P = (p_r - p_l)^2 - (q_r - q_l)$rewrite this to get $P = -2p_l(p_r) + (p_l^2 + q_l) + (p_r^2 - q_r)$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$.
•  » » 4 weeks ago, # ^ |   0 thanks for the solution
 » 4 weeks ago, # |   0 send the problem link or otherwise how do we know you arent cheating from some online contest