1ST_MATHER's blog

Help me with this problem
By 1ST_MATHER, history, 9 days ago, In English

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

Tags dp
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I have an idea to use dp but haven't built a formula yet

→ Reply
»
9 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think it uses Kadane's DP, but you have to keep track of the optimal range throughout the process.

#include <bits/stdc++.h>
#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<int> a(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }

  function<int()> 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<int()> 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;
}
→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

send the problem link or otherwise how do we know you arent cheating from some online contest

→ Reply