Redaksiya

Group 1: $n\le 3$.

Let's take a look at both cases ($n=2$ and $n=3$):

• $n=2$: the only way to perform operations in this case is to take subarrays $[a_1]$ and $[a_2]$ and to remove both elements from their subarrays. This way, both parts become empty, their sums become $0$'s and the difference between them is always $|0-0|=0$;

• $n=3$: since two elements from the initial array are removed, one element remains. This element belongs to one of the subarrays, and the other subarray is empty. If this one remaining elements is $x$, then the answer is $|0-x|=|x|$. Actually, any of three elements of the array can be such $x$. Here is how:

  1. $[a_1,a_2,a_3]$ -> $[a_1,a_2]$, $[a_3]$ -> $[a_1]$, $[]$

  2. $[a_1,a_2,a_3]$ -> $[a_1,a_2]$, $[a_3]$ -> $[a_2]$, $[]$

  3. $[a_1,a_2,a_3]$ -> $[a_1]$, $[a_2,a_3]$ -> $[]$, $[a_3]$

  Thus, the answer for this case is $max(|a_1|,|a_2|,|a_3|)$.

Time and memory complexity: $O(n)$.

Group 2: all elements of the array are equal.

In this group, we can notice that, in case of choosing $k$ as a dividing index and removing any element from both resulting subarrays, the sums of parts are guaranteed to be $a_1\cdot (k-1)$ and $a_1\cdot (n-k-1)$ and the difference between them is $|a_1\cdot ((n-k-1)-(k-1))|=|a_1\cdot (n-2\cdot k)|$.

$a_1$ and $n$ are constants, thus our task now is to choose such $k$ that $|n-2\cdot k|$ reaches its maximum value (since the larger are absolute values of the multiples — the larger is the absolute value of their product).

$1\le k\le n-1$, thus the value of $(n-2\cdot k)$ varies from $n-2\cdot (n-1)=-n+2$ to $n-2\cdot 1=n-2$. The maximum absolute value of a number from this range is $n-2$, thus the answer for the group is $a_1\cdot (n-2)$.

Time and memory complexity: $O(n)$ or $O(1)$ (we do not need to read the whole array, just the first number is enough).

Group 3: all elements of the array are positive.

Knowing that, in this group it is enough to check both first and last elements of the array as the single element of a subarray and check all other elements as if they were the one removed from the other subarray.

Time and memory complexity: $O(n)$.

Group 4: the array is non-decreasing.

If there are numbers of only one sign (including zeros as the numbers of the same sign as non-zero numbers) — then the solution is the same as for the previous group.

Otherwise, let's think about the case when there are no zeros in the array. The most optimal way to divide the array here is actually to take all the negative elements to one part and to remove the largest one of them and to take all the positive elements to another part and to remove the smallest one of them.

If there is one zero in the array — then we can try to consider it as a negative and as a positive number (in both cases it will be the one element removed from its part).

If there are two or more zeros in the array — then we can distribute them in any way such that at least one of them is in the first part and at least one is in the second part.

Group 5: $n\le 300$.

To solve this group, we can, in fact, just do what is said in the statement: iterate through all the possible $k$'s (from $1$ to $n-1$) to divide the initial array, then try all the combinations of $i$ and $j$ such that $i\le k$ and $j>k$ and update the answer with the difference we get with these values. To keep the sum of elements of both subarrays before deleting $i$-th and $j$-th elements, we can store the current $sum\_left$, the $sum$ of the whole array, update the $sum\_left$ when moving $k$ and take $sum\_right=sum-sum\_left$. To update the answer, we can just remove $a_i$ and $a_j$ from sums of their subarrays (take the value $|(sum\_left-a_i)-(sum-sum\_left-a_j)|$).

Time complexity: $O(n^3)$

Memory complexity: $O(n)$

Group 6: $n\le 2000$.

Thus, the optimization we can do for the solution from the previous group, is to only update the answer using $(i=left\_max;j=right\_min)$ and vice versa $(i=left\_min;j=right\_max)$. To keep such indices, we can recalculate them for every iteration of $k$ in linear time. Updating answer is just handling $2$ cases with formulas, which is $O(2)=O(1)$.

Time complexity: $O(n^2)$

Memory complexity: $O(n)$

Group 7: no additional constraints.

The solution for this group is the same as for the previous one, but we can update $left\_min$ and $left\_max$ indices while moving through the $k$'s and take the same values for the right part using multiset or suffix minimums and maximums.

Full solution with $O(n)$ time complexity (C++):

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 12;
const int inf = 1e9 + 7;

int n;
int a[N];

int L_mn = inf, L_mx = -inf;
int R_mn[N], R_mx[N];

ll sum = 0, L_sum = 0;
ll ans = 0;

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) {
    	cin >> a[i];
    	sum += a[i];
    }

    R_mn[n - 1] = R_mx[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--) {
    	R_mn[i] = min(R_mn[i + 1], a[i]);
    	R_mx[i] = max(R_mx[i + 1], a[i]);
    }

    for (int i = 0; i < n - 1; i++) {
    	L_sum += a[i];
    	
    	L_mn = min(L_mn, a[i]);
    	L_mx = max(L_mx, a[i]);

    	ans = max(ans, abs((L_sum - L_mn) - (sum - L_sum - R_mx[i + 1])));
    	ans = max(ans, abs((L_sum - L_mx) - (sum - L_sum - R_mn[i + 1])));
    }

    cout << ans << endl;
}

Time complexity: $O(nlogn)$ or $O(n)$

Memory complexity: $O(n)$