053 Maximum Subarray

#dp#dynamicprogramming#greedy#runningsum#leetcode Problem Link Given an integer array nums, find the subarray with the largest sum, and return its sum.

Solution §

Use dynamic programming and a ‘running sum’. If running sum is less than 0, then reset it. Also every iteration update ‘max’ subarray answer.

Scratch §

2 indices, left and right marking end and beginning of subarray.

For each iteration:

• Slide right index right
  • If sum increases, keep it
  • If sum decreases:
    • If current sum value < index[right]
      • Slide left pointer right until sum value > index[right]
      • If it never does so, we basically restart the subarray at index[right]

[-2, 1, -3, 4, -1, 2, 1, -5, 4] Brute Force: All possible subarrays $O(n^2)$

DP Approach: Run a ‘sum’ on a prefix, if that sum is < 0, then restart it (since adding a negative or positive will not be more beneficial than just restarting)

EX (how ‘dp’ array looks) -2, 1, -3, 4, 3, 5, 6, 1, 5

-2 -1