Let $ a = [a_1, a_2, \dots, a_n] $ be an array of $ n $ integers, where $ 2 \leq n \leq 10^5 $ and $ -10^9 \leq a_i \leq 10^9 $.
Define the function $ f(l, r) $ for $ 1 \leq l < r \leq n $ as:
$$
f(l, r) = \left| \sum_{i=l+1}^{r-1} a_i \right|
$$
That is, $ f(l, r) $ is the absolute value of the sum of elements strictly between indices $ l $ and $ r $ (excluding $ a_l $ and $ a_r $).
**Objective:**
Find the maximum value of $ f(l, r) $ over all valid pairs $ (l, r) $ with $ 1 \leq l < r \leq n $.
---
**Equivalent Reformulation:**
Let $ S(i, j) = \sum_{k=i}^{j} a_k $ denote the sum of subarray from index $ i $ to $ j $ (inclusive).
Then:
$$
f(l, r) = \left| S(l+1, r-1) \right|
$$
We seek:
$$
\max_{1 \leq l < r \leq n} \left| S(l+1, r-1) \right|
$$
Note: When $ r = l+1 $, the inner sum is over an empty range, so $ f(l, l+1) = 0 $.
Thus, the problem reduces to:
**Find the maximum absolute value of the sum of any contiguous subarray of length at least 1 (i.e., excluding single-element subarrays from being considered as inner sums), but note that the inner sum $ S(l+1, r-1) $ can be of length 0 (yielding 0) or more.**
But since we are taking absolute value and seeking maximum, we can rephrase:
Let $ b $ be the array of all contiguous subarray sums of $ a $, excluding those of length 0 and those that correspond to $ l+1 > r-1 $ (i.e., inner sums of length ≥ 1). Then we want $ \max |s| $ over all such $ s \in b $.
Alternatively, since $ S(l+1, r-1) = S(1, r-1) - S(1, l) $, we can define prefix sums:
Let $ p_0 = 0 $, and $ p_i = \sum_{k=1}^{i} a_k $ for $ 1 \leq i \leq n $.
Then:
$$
S(l+1, r-1) = p_{r-1} - p_l
$$
So:
$$
f(l, r) = |p_{r-1} - p_l|, \quad \text{for } 0 \leq l < r-1 \leq n-1
$$
Let $ i = l $, $ j = r-1 $. Then the constraint $ 1 \leq l < r \leq n $ becomes:
- $ l \in [0, n-2] $ (since $ l = 0 $ corresponds to $ a_1 $ being excluded, $ l = n-2 $ means $ r = n $)
- $ j \in [1, n-1] $
- and $ i < j $
So we are to compute:
$$
\max_{0 \leq i < j \leq n-1} |p_j - p_i|
$$
This is the well-known problem: **Maximum absolute difference between two prefix sums with $ i < j $**.
Which is equivalent to:
$$
\max_{0 \leq i < j \leq n-1} (p_j - p_i) \quad \text{and} \quad \max_{0 \leq i < j \leq n-1} (p_i - p_j)
$$
So:
$$
\max \left( \max_{j} p_j - \min_{i < j} p_i, \max_{i} p_i - \min_{j > i} p_j \right)
$$
But since we are taking absolute value, it's simply:
$$
\max_{0 \leq i < j \leq n-1} |p_j - p_i| = \max(p_{\max} - p_{\min})
$$
where $ p_{\max} = \max_{0 \leq k \leq n-1} p_k $, $ p_{\min} = \min_{0 \leq k \leq n-1} p_k $, and we require that the maximum occurs for some $ i < j $, which is guaranteed if we consider the global min and max over the entire prefix array (as long as the min occurs before the max, or vice versa — but if not, we can still compute the maximum difference over all pairs).
Actually, the maximum absolute difference between any two prefix sums $ p_i, p_j $ with $ i < j $ is equal to:
$$
\max\left( \max_{0 \leq j \leq n-1} p_j - \min_{0 \leq i < j} p_i, \max_{0 \leq i \leq n-1} p_i - \min_{i < j \leq n-1} p_j \right)
$$
But a simpler and correct approach is:
> The maximum value of $ |p_j - p_i| $ for $ 0 \leq i < j \leq n-1 $ is equal to $ \max p_k - \min p_k $ over $ k \in [0, n-1] $, **provided** that the global maximum occurs after the global minimum. If not, we need to ensure $ i < j $.
But note: we are allowed to choose any $ i < j $. So the maximum difference $ p_j - p_i $ over $ i < j $ is:
$$
\max_{j} \left( p_j - \min_{i < j} p_i \right)
$$
Similarly, the maximum of $ p_i - p_j $ for $ i < j $ is:
$$
\max_{i} \left( p_i - \min_{j > i} p_j \right)
$$
But since we take absolute value, we can compute:
$$
\max \left( \max_{0 \leq i < j \leq n-1} (p_j - p_i), \max_{0 \leq i < j \leq n-1} (p_i - p_j) \right)
= \max_{0 \leq i, j \leq n-1, i \ne j} |p_i - p_j|
$$
And since the maximum absolute difference between any two elements in a set is $ \max - \min $, we can compute:
Let $ P = \{ p_0, p_1, \dots, p_{n-1} \} $
Then:
$$
\max_{0 \leq i < j \leq n-1} |p_j - p_i| = \max(P) - \min(P)
$$
**Why?** Because if the global maximum occurs at index $ j $ and global minimum at index $ i $, and if $ i < j $, then we are done. If $ i > j $, then we can still find some pair $ i' < j' $ such that $ p_{j'} - p_{i'} = \max(P) - \min(P) $, because the maximum difference in absolute value over all unordered pairs is always $ \max - \min $, and since we are allowed to pick any $ i < j $, as long as $ \max $ and $ \min $ are in the prefix array, and we can always find a pair where the larger one comes after the smaller one (or vice versa for negative), but the absolute value makes it symmetric.
Actually, **this is not always true** if the global min occurs after the global max. For example: $ p = [10, 1, 5] $, then $ \max = 10 $, $ \min = 1 $, but $ \max - \min = 9 $, but if the max is at index 0 and min at index 1, then we cannot use $ p_0 - p_1 $ as $ i < j $, but we can use $ p_2 - p_1 = 4 $, or $ p_0 - p_1 = 9 $, but $ i=0, j=1 $, and $ i < j $, so we **can** use it.
Wait — $ i $ and $ j $ are indices in the prefix array, and we require $ i < j $, meaning the index of the first prefix sum is less than the index of the second.
So if $ p_i = \min $ at index $ i $, $ p_j = \max $ at index $ j $, and $ i < j $, then $ p_j - p_i = \max - \min $ is valid.
If $ i > j $, then $ p_i - p_j = \max - \min $, but $ i > j $, so we cannot use that pair because we require $ i < j $ in the pair $ (i, j) $ for $ p_j - p_i $.
Wait — in our expression $ f(l, r) = |p_{r-1} - p_l| $, and we have $ l < r-1 $, so $ i = l $, $ j = r-1 $, and $ i < j $. So we require the index of the first prefix to be less than the index of the second.
Therefore, the maximum value of $ p_j - p_i $ for $ i < j $ is:
$$
\max_{0 \leq i < j \leq n-1} (p_j - p_i)
$$
And the maximum value of $ p_i - p_j $ for $ i < j $ is:
$$
\max_{0 \leq i < j \leq n-1} (p_i - p_j) = - \min_{0 \leq i < j \leq n-1} (p_j - p_i)
$$
But we take absolute value, so:
$$
\max_{0 \leq i < j \leq n-1} |p_j - p_i| = \max\left( \max_{i<j} (p_j - p_i), \max_{i<j} (p_i - p_j) \right)
= \max\left( \max_{i<j} (p_j - p_i), \max_{i<j} (p_i - p_j) \right)
$$
But note: $ \max_{i<j} (p_i - p_j) = \max_{i<j} -(p_j - p_i) = - \min_{i<j} (p_j - p_i) $
So the maximum absolute value is the maximum of:
- The maximum positive difference $ \max_{i<j} (p_j - p_i) $
- The maximum negative difference's absolute value: $ \max_{i<j} (p_i - p_j) = \max_{i<j} (-(p_j - p_i)) $
But this is equal to:
$$
\max\left( \max_{i<j} (p_j - p_i), \max_{i<j} (p_i - p_j) \right) = \max\left( \max_{i<j} (p_j - p_i), \max_{i<j} (p_i - p_j) \right)
$$
And since $ \max_{i<j} (p_i - p_j) = \max_{i<j} |p_i - p_j| $ when $ p_i > p_j $, we can compute both.
But there is a standard result:
> The maximum absolute difference between any two elements in a sequence, with the constraint that the first element comes before the second, is equal to the maximum difference between any two prefix sums where the later one is subtracted by the earlier one, and we take the maximum over all such pairs.
Actually, the maximum value of $ |p_j - p_i| $ for $ i < j $ is equal to:
$$
\max\left( \max_{0 \leq j \leq n-1} p_j - \min_{0 \leq i < j} p_i, \max_{0 \leq i \leq n-1} p_i - \min_{i < j \leq n-1} p_j \right)
$$
But a simpler and correct method is:
Let $ m = \min_{0 \leq k \leq n-1} p_k $, $ M = \max_{0 \leq k \leq n-1} p_k $
Then the maximum absolute difference over all $ i < j $ is not necessarily $ M - m $, because if $ m $ occurs after $ M $, then $ M - m $ cannot be achieved with $ i < j $.
But we can compute:
- $ \text{max\_diff} = 0 $
- $ \text{min\_so\_far} = p_0 $
- For $ j = 1 $ to $ n-1 $:
- $ \text{max\_diff} = \max(\text{max\_diff}, p_j - \text{min\_so\_far}) $
- $ \text{min\_so\_far} = \min(\text{min\_so\_far}, p_j) $
Then the maximum of $ p_j - p_i $ for $ i < j $ is this `max_diff`.
Similarly, to get the maximum of $ p_i - p_j $ for $ i < j $, we can reverse: compute maximum of $ p_i - p_j $ for $ i < j $, which is equivalent to computing $ \max_{i<j} (p_i - p_j) = \max_{i<j} (-(p_j - p_i)) $, so we can compute:
- $ \text{max\_so\_far} = p_0 $
- For $ j = 1 $ to $ n-1 $:
- $ \text{max\_diff\_neg} = \max(\text{max\_diff\_neg}, \text{max\_so\_far} - p_j) $
- $ \text{max\_so\_far} = \max(\text{max\_so\_far}, p_j) $
Then the answer is:
$$
\max(\text{max\_diff}, \text{max\_diff\_neg})
$$
But note: $ \text{max\_diff\_neg} = \max_{i<j} (p_i - p_j) $, and since we take absolute value, we want the maximum of the absolute values, so:
$$
\boxed{ \max\left( \max_{0 \leq i < j \leq n-1} (p_j - p_i), \max_{0 \leq i < j \leq n-1} (p_i - p_j) \right) }
$$
Which is equivalent to:
$$
\boxed{ \max_{0 \leq i < j \leq n-1} |p_j - p_i| }
$$
And this can be computed in $ O(n) $ time by:
1. Compute prefix sums $ p_0, p_1, \dots, p_{n-1} $, where $ p_0 = 0 $, $ p_i = p_{i-1} + a_i $ for $ i = 1 $ to $ n-1 $.
2. Compute:
- $ \text{pos\_max} = \max_{i<j} (p_j - p_i) $ via scanning left to right, tracking min prefix so far.
- $ \text{neg\_max} = \max_{i<j} (p_i - p_j) $ via scanning left to right, tracking max prefix so far.
Then answer = $ \max(\text{pos\_max}, \text{neg\_max}) $
But note: $ \text{neg\_max} = \max_{i<j} (p_i - p_j) = \max_{i<j} |p_i - p_j| $ when $ p_i > p_j $, so we are covering both cases.
Alternatively, since $ \max_{i<j} |p_j - p_i| = \max( \max_{i<j} (p_j - p_i), \max_{i<j} (p_i - p_j) ) $, and both can be computed in one pass each.
However, note that $ \max_{i<j} |p_j - p_i| $ is equal to the maximum of:
- $ \max p_k - \min p_k $, if the min occurs before the max
- or the maximum gap where a high value is followed by a low value
But the standard solution to "maximum difference between two elements with smaller index first" is to compute:
$$
\max_{j} (p_j - \min_{i < j} p_i)
$$
This gives the maximum positive difference.
Similarly, to get the maximum negative difference in absolute value, we compute:
$$
\max_{j} (\max_{i < j} p_i - p_j)
$$
So final algorithm:
Let $ p[0] = 0 $
For $ i = 1 $ to $ n-1 $:
$ p[i] = p[i-1] + a[i] $
Then:
- $ \min\_prev = p[0] $
- $ \max\_pos = 0 $
- For $ j = 1 $ to $ n-1 $:
- $ \max\_pos = \max(\max\_pos, p[j] - \min\_prev) $
- $ \min\_prev = \min(\min\_prev, p[j]) $
- $ \max\_prev = p[0] $
- $ \max\_neg = 0 $
- For $ j = 1 $ to $ n-1 $:
- $ \max\_neg = \max(\max\_neg, \max\_prev - p[j]) $
- $ \max\_prev = \max(\max\_prev, p[j]) $
Answer: $ \max(\max\_pos, \max\_neg) $
But note: $ \max\_neg $ is the maximum of $ p_i - p_j $ for $ i < j $, which is the maximum absolute value when the prefix decreases.
This is correct.
But observe: since we are taking absolute value, and the two cases are symmetric, we can also note that:
$$
\max_{i<j} |p_j - p_i| = \max_{i,j \in [0, n-1], i \ne j} |p_i - p_j|
$$
because if the global max and min occur in any order, and since we are allowed to pick any $ i < j $, then the maximum absolute difference over all unordered pairs is $ \max p_k - \min p_k $, and if the min occurs after the max, then we cannot use that pair, but we can still achieve the same value if there exists some pair where the difference is $ \max - \min $, but only if the max occurs before the min? No.
Counterexample:
Let $ p = [5, 1, 3] $
Then $ \max p = 5 $, $ \min p = 1 $, difference = 4
But $ p_0 = 5 $, $ p_1 = 1 $, $ i=0, j=1 $: $ |p_1 - p_0| = 4 $, and $ i < j $, so it's allowed.
So even if the min comes after the max, as long as we are taking absolute value and the indices satisfy $ i < j $, we can still get $ |p_j - p_i| = \max - \min $ if the max is at an earlier index and min at a later one.
Wait — in this case, $ p_0 = 5 $, $ p_1 = 1 $, then $ |p_1 - p_0| = 4 = 5 - 1 $, which is $ \max - \min $, and $ i=0 < j=1 $, so it's valid.
Another example: $ p = [1, 5, 3] $
$ \max = 5 $, $ \min = 1 $, difference = 4
$ p_0 = 1 $, $ p_1 = 5 $, $ |p_1 - p_0| = 4 $, $ i=0 < j=1 $, valid.
Another: $ p = [3, 1, 5] $
$ \max = 5 $, $ \min = 1 $, difference = 4
Can we get 4?
$ |p_2 - p_1| = |5 - 1| = 4 $, and $ i=1 < j=2 $, valid.
So in all cases, as long as the global maximum and global minimum appear somewhere in the prefix array, then the pair consisting of the index of the global min and global max will have $ |p_j - p_i| = \max - \min $, and since the two indices are distinct, one must come before the other. So we can always find a pair $ i < j $ such that $ |p_j - p_i| = \max p_k - \min p_k $.
Therefore:
$$
\boxed{ \max_{0 \leq i < j \leq n-1} |p_j - p_i| = \max_{0 \leq k \leq n-1} p_k - \min_{0 \leq k \leq n-1} p_k }
$$
**Final Answer:**
Compute prefix sums $ p_0 = 0, p_1 = a_1, p_2 = a_1 + a_2, \dots, p_{n-1} = \sum_{i=1}^{n-1} a_i $
(Note: $ p_i = \sum_{k=1}^{i} a_k $ for $ i \geq 1 $, and $ p_0 = 0 $)
Then:
$$
\boxed{ \max_{0 \leq i \leq n-1} p_i - \min_{0 \leq i \leq n-1} p_i }
$$
This is the maximum value of $ f(l, r) $.