Maximum absolute sum of a subarray =Max prefix sum — Min prefix sum(prefix sum includes zero).
# | User | Rating |
---|---|---|
1 | jiangly | 3845 |
2 | tourist | 3798 |
3 | orzdevinwang | 3706 |
4 | jqdai0815 | 3682 |
5 | ksun48 | 3589 |
6 | Ormlis | 3532 |
7 | Benq | 3468 |
8 | Radewoosh | 3463 |
9 | ecnerwala | 3451 |
10 | Um_nik | 3450 |
# | User | Contrib. |
---|---|---|
1 | cry | 165 |
2 | Qingyu | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 157 |
5 | Dominater069 | 156 |
6 | adamant | 154 |
7 | djm03178 | 151 |
8 | luogu_official | 149 |
9 | awoo | 147 |
10 | TheScrasse | 145 |
Maximum absolute sum of a subarray =Max prefix sum — Min prefix sum(prefix sum includes zero).
Name |
---|
Well this statement isn't exactly true, let me show you why.
take the following array {1,2,-10}
the maximum subarray sum is 1+2=3
but according to your formula its max prefix — min prefix = 3-(-7)=11
which obviously isn't true.
What you're looking for is the maximum value of a prefix sums minus the min prefix sum that ends before it
.
It's the maximum absolute sum of a subarray, so for your array, that would be abs(sum({-10})) = 10, and indeed 3-(-7) = 10.
Oh worry i misread
Notation: n length of array, ai (0≤i<n) ith element, slr=∑l≤j<raj (0≤l≤r≤n) sum of elements from l to r, pi=s0i prefix sum
Part 1: maximum absolute sum of a subarray ≥ max prefix sum − min prefix sum
Let pM and pm be the maximum and minimum prefix sum, respectively. WLOG assume M≤m. Then max.
Part 2: maximum absolute sum of a subarray \le max prefix sum - min prefix sum
Let L, R (L\le R) be indices such that \max(|s_{lr}|) = |s_{LR}|. WLOG assume p_L \le p_R. Then, \max(|s_{lr}|) = |s_{LR}| = |p_R - p_L| = p_R - p_L \le \max(p_i) - \min(p_i).