In the last question of DSA Monday Munch 11 – Maximize Subarray Difference, the statement says:
Find the maximum possible absolute difference between the sums of two non-empty, non-overlapping contiguous subarrays P and Q, where P occurs before Q.
According to the given constraints: 1≤i≤j<k≤l≤N
For the sample array:
[10,−20,30,−40,50]
the explanation mentions the optimal choice as:
-
P = [30], sum = 30
-
Q = [−40], sum = -40
giving:
∣30−(−40)∣ = 70
However, there is a better valid choice:
-
P = [−40], sum = -40
-
Q = [50], sum = 50
Since P occurs before Q (indices 4 and 5), this satisfies the condition: 4<5
The absolute difference is:
∣−40−50∣=90
Therefore, based on the problem statement, the maximum possible difference should be 90, not 70.
Could someone confirm if there is any missing constraint in the original problem, or is the sample explanation incorrect?