P15615 [ICPC 2021 Jakarta R] Maxdifficent Group

Given an array of integers $A_{1..N}$ where $N \geq 2$. Each element in $A$ should be assigned into a group while satisfying the following rules. - Each element belongs to exactly one group. - If $A_{i}$ and $A_{j}$ where $i < j$ belongs to the same group, then $A_{k}$ where $i \leq k \leq j$ also belongs to the same group as $A_{i}$ and $A_{j}$. - There is at least one pair of elements that belong to a different group. Let $G_{i}$ denotes the group ID of element $A_{i}$. The cost of a group is equal to the sum of all elements in $A$ that belong to that group. $$\text{cost}(x) = \sum_{i \text{ s.t. } G_{i} = x} A_{i}$$ Two different group IDs, $G_{i}$ and $G_{j}$ (where $G_{i} \neq G_{j}$), are **adjacent** if and only if $G_{k}$ is either $G_{i}$ or $G_{j}$ for every $i \leq k \leq j$. Finally, the $\text{diff}()$ value of two group IDs $x$ and $y$ is defined as the absolute difference between $\text{cost}(x)$ and $\text{cost}(y)$. $$\text{diff}(x, y) = |\text{cost}(x) - \text{cost}(y)|$$ Your task in this problem is to find a group assignment such that the largest $\text{diff}()$ value between any pair of adjacent group IDs is maximized; you only need to output the largest $\text{diff}()$ value. For example, let $A_{1..4} = \{100, -30, -20, 70\}$. There are $8$ ways to assign each element in $A$ into a group in this example; some of them are shown as follows. - $G_{1..4} = \{1, 2, 3, 4\}$. There are $3$ pairs of group IDs that are adjacent and their $\text{diff}()$ values are: - $\text{diff}(1, 2) = |\text{cost}(1) - \text{cost}(2)| = |(100) - (-30)| = 130$, - $\text{diff}(2, 3) = |\text{cost}(2) - \text{cost}(3)| = |(-30) - (-20)| = 10$, and - $\text{diff}(3, 4) = |\text{cost}(3) - \text{cost}(4)| = |(-20) - (70)| = 90$. The largest $\text{diff}()$ value in this group assignment is $130$. - $G_{1..4} = \{1, 2, 2, 3\}$. There are $2$ pairs of group IDs that are adjacent and their $\text{diff}()$ values are: - $\text{diff}(1, 2) = |\text{cost}(1) - \text{cost}(2)| = |(100) - (-30 + (-20))| = 150$, and - $\text{diff}(2, 3) = |\text{cost}(2) - \text{cost}(3)| = |(-30 + (-20)) - (-20)| = 70$. The largest $\text{diff}()$ value in this group assignment is $150$. The other $6$ group assignments are: $G_{1..4} = \{1, 1, 1, 2\}$, $G_{1..4} = \{1, 1, 2, 2\}$, $G_{1..4} = \{1, 2, 2, 2\}$, $G_{1..4} = \{1, 1, 2, 2\}$, $G_{1..4} = \{1, 1, 2, 3\}$, and $G_{1..4} = \{1, 2, 3, 3\}$. Among all possible group assignments in this example, the maximum largest $\text{diff}()$ that can be obtained is $150$ from the group assignment $G_{1..4} = \{1, 2, 2, 3\}$.

Input begins with a line containing an integer $N$ ($2 \leq N \leq 100\,000$) representing the number of elements in array $A$. The next line contains $N$ integers $A_{i}$ ($-10^{6} \leq A_{i} \leq 10^{6}$) representing the array $A$.

Output contains an integer in a line representing the maximum possible largest $\text{diff}()$ that can be obtained from a group assignment.

#### Explanation for the sample input/output #2 The maximum possible largest $\text{diff}()$ of $46$ can be obtained from the group assignment $G_{1..5} = \{1, 1, 1, 1, 2\}$. The $\text{diff}()$ value of the only adjacent group IDs is: $\text{diff}(1, 2) = 46$. #### Explanation for the sample input/output #3 The maximum possible largest $\text{diff}()$ of $70$ can be obtained from the group assignment $G_{1..6} = \{1, 2, 2, 2, 3, 4\}$. The $\text{diff}()$ values of any two adjacent group IDs are: $\text{diff}(1, 2) = 55$, $\text{diff}(2, 3) = 70$, and $\text{diff}(3, 4) = 35$.