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.
Thank you in advance!
try using long long instead of int, you might be overflowing
The idea is simply just wrong.
Consider this test case:
(I know $$$m = 0$$$ isn't allowed in the statement but I assume your code works there correctly)
Can you see why this happens?