Challenge Description
Solution with linear scan
Use a variable sum
to store current sum of arr(0..index), if sum
is less than zero, it’s better to drop the previous sum, set current index as the new starting index.
Time complexity: $O(N)$

Approach with divide and conquer
Just as quicksort, we divide the array into two parts, then recursive compute the maximum sum for each parts. The tricky operation is merge, we need to loop from m1
to l
to find the possible maximum value in left part, and do the same thing for right part.
Then, we compare lmax
, rmax
, and ml + mr + nums[m]
(which means combine middle with left part and right part).
The overall time complexity is $O(NlogN)$.

Join my Email List for more insights, It's Free!😋