Maximum subarray

main.py

class Solution:
    def without_dp_array(self, arr: List[int]) -> int:
        n = len(arr)
        best = max(arr)
        curr = 0
        for ele in arr:
            if ele > curr + ele:
                curr = ele
            else:
                curr += ele
            best = max(best, curr)
        return best

    def with_dp_array(self, arr: List[int]) -> int:
        n = len(arr)
        # dp[i] = max sum for arr[...i]
        dp = [0] * n
        dp[0] = arr[0]
        for i in range(1, n):
            dp[i] = max(dp[i - 1] + arr[i], arr[i])
        return max(dp)

Divide and conquer for this is also quite interesting: (https://www.youtube.com/watch?v=yBCzO0FpsVc)
maxSum(l, r) = max(maxSum(0, l), maxSum(r, n), maxSuff(0, l) + maxPref(r, n)
This would be nlogn