[Help] Segment with the Maximum Sum
I am getting WA on test 28 of this problem. Would really appreciate all the help.
My Approach
Basically, I am partitioning each segment $$$[l \ldots r]$$$ into three partitions, $$$p_1, p_2, p_3$$$ where
$$$p_2$$$ = maximum subarray sum in $$$[l \ldots r]$$$
$$$p_1$$$ = remaining left side sum
$$$p_3$$$ = remaining right side sum
$$$p_1+p_2+p_3 = \sum{a[l \ldots r]}$$$
Now to combine two arrays, the maximum subarray sum of the combined array would be $$$\max{(p_2^{(1)}, p_2^{(2)}, p_2^{(1)}+p_3^{(1)}+p_1^{(2)}+p_2^{(2)})}$$$.
The remaining left and right side parts can be maintained easily.
The final answer will be $$$p_2$$$ of the root of the segment tree.
My Code
Thank you in advance!
