<filename>Problems/BinarySearch/Hard/SplitArrayLargestSum/split_array_largest_sum.py
from functools import lru_cache
from typing import List


# DP - Top-Down
def splitArray(self, nums: List[int], m: int) -> int:
    n = len(nums)
    ps = [0]
    for num in nums:
        ps.append(ps[-1] + num)

    @lru_cache(None)
    def dp(i: int, c: int) -> int:
        if i == n:
            return 0
        if c == 1:
            return ps[-1] - ps[i]

        ans = float('inf')
        for j in range(i, n):
            l, r = ps[j + 1] - ps[i], dp(j + 1, c - 1)
            ans = min(ans, max(l, r))
            if l > r:
                break

        return ans

    return dp(0, m)

# BST
def splitArray(self, nums: List[int], m: int) -> int:
    def helper(c: int, mid: int):
        cur_sum, cuts = 0, 0

        for x in nums:
            cur_sum += x
            if cur_sum > mid:
                cur_sum = x
                cuts += 1

        return cuts + 1 <= c

    l, r, res = max(nums), sum(nums), -1
    while l <= r:
        mid = (l + r) >> 1
        if helper(m, mid):
            ans, r = mid, mid - 1
        else:
            l = mid + 1
    return ans
<filename>Problems/BinarySearch/Hard/SplitArrayLargestSum/split_array_largest_sum.py
from functools import lru_cache
from typing import List


# DP - Top-Down
def splitArray(self, nums: List[int], m: int) -> int:
    n = len(nums)
    ps = [0]
    for num in nums:
        ps.append(ps[-1] + num)

    @lru_cache(None)
    def dp(i: int, c: int) -> int:
        if i == n:
            return 0
        if c == 1:
            return ps[-1] - ps[i]

        ans = float('inf')
        for j in range(i, n):
            l, r = ps[j + 1] - ps[i], dp(j + 1, c - 1)
            ans = min(ans, max(l, r))
            if l > r:
                break

        return ans

    return dp(0, m)

# BST
def splitArray(self, nums: List[int], m: int) -> int:
    def helper(c: int, mid: int):
        cur_sum, cuts = 0, 0

        for x in nums:
            cur_sum += x
            if cur_sum > mid:
                cur_sum = x
                cuts += 1

        return cuts + 1 <= c

    l, r, res = max(nums), sum(nums), -1
    while l <= r:
        mid = (l + r) >> 1
        if helper(m, mid):
            ans, r = mid, mid - 1
        else:
            l = mid + 1
    return ans
# DP - Top-Down # BST