""" 
keys: 
Solutions:
Similar:
T:
S:
"""

from typing import List


class Solution:

    # huahua dp
    def splitArray(self, nums: List[int], m: int) -> int:
        
        def helper(k, j):
            if j == 1:  # j as the number of splits, keep only one array
                return culSum[k]
            if j > k + 1:
                return float("inf")
            if dp[k][j] != float("inf"):
                return dp[k][j]
            res = float("inf")
            for i in range(k):
                res = min(res, max(helper(i, j - 1), culSum[k] - culSum[i]))
            dp[k][j] = res
            return dp[k][j]


        n = len(nums)
        culSum = [0] * (n + 1)
        culSum[0] = nums[0]
        dp = [[0] * (m + 1) for _ in range(n)]
        for i in range(1, n):
            culSum[i] = culSum[i - 1] + nums[i]

        return helper(n - 1, m)



    # official binary search + greedy
    def splitArray(self, nums: List[int], m: int) -> int:
        l, r = 0, 0
        n = len(nums)
        for i in range(n):
            r += nums[i]
            if l < nums[i]:
                l = nums[i]

        res = r
        while l <= r:
            mid = l + (r - l) // 2
            sum_ = 0
            ct = 1
            for i in range(n):
                if sum_ + nums[i] > mid:
                    ct += 1
                    sum_ = nums[i]
                else:
                    sum_ += nums[i]

            if ct <= m:
                res = min(res, mid)
                r = mid - 1
            else:
                l = mid + 1
        return res


    # official dp, TLE
    # T: O(m * n^2)
    # dp[i][j] to be the minimum largest subarray sum for splitting nums[0..i] into j parts
    def splitArray(self, nums: List[int], m: int) -> int:
        n = len(nums)
        dp = [[float("inf")] * (m + 1) for _ in range(n + 1)]  # n+1 rows, m+1 cols
        sub = [0] * (n + 1)  # culSum, used to calculate the sum of subarray

        for i in range(n):
            sub[i + 1] = sub[i] + nums[i]

        dp[0][0] = 0
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                for k in range(i):
                    dp[i][j] = min(dp[i][j], max(dp[k][j-1], sub[i] - sub[k]))
        return dp[n][m]



    # official backtrack
    # T: O(n^m), n as #elements. Combinations of selecting m-1 out of n-1.
    def splitArray(self, nums: List[int], m: int) -> int:

        def dfs(i, ctSub, curSum, curMax):
            nonlocal res
            # i for curIdx
            if i == n and ctSub == m:
                res = min(res, curMax)
                return

            if i == n:
                return 

            if i > 0:
                dfs(i+1, ctSub, curSum + nums[i], max(curMax, curSum + nums[i]))

            if ctSub < m:
                dfs(i+1, ctSub+1, nums[i], max(curMax, nums[i]))


        res = float("inf")
        n = len(nums)
        dfs(0, 0, 0, 0)
        return res
        
        