<p>Given an integer array <code>nums</code> and an integer <code>k</code>, split <code>nums</code> into <code>k</code> non-empty subarrays such that the largest sum of any subarray is <strong>minimized</strong>.</p>

<p>Return <em>the minimized largest sum of the split</em>.</p>

<p>A <strong>subarray</strong> is a contiguous part of the array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [7,2,5,10,8], k = 2
<strong>Output:</strong> 18
<strong>Explanation:</strong> There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5], k = 2
<strong>Output:</strong> 9
<strong>Explanation:</strong> There are four ways to split nums into two subarrays.
The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>
	<li><code>1 &lt;= k &lt;= min(50, nums.length)</code></li>
</ul>

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        return self.fun2(nums, k)

    def fun2(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [[float("inf")] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 0

        sms = [0]
        for d in nums:
            sms.append(sms[-1] + d)

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

        return dp[n][k]

    def fun1(self, nums: List[int], k: int) -> int:
        sm = sum(nums)
        left = sm // k
        right = sm

        def check(nums, k, mid):
            cnt = 1
            ans = 0
            res = 0
            for d in nums:
                ans += d
                if ans > mid:
                    res = max(ans - d, res)
                    cnt += 1
                    ans = d
                    if cnt > k:
                        return False, 0

            return (cnt <= k, max(res, ans))

        res = sm
        while left < right:
            mid = left + (right - left) // 2
            flag, ans = check(nums, k, mid)
            if flag:
                right = mid
                res = min(res, ans)
            else:
                left = mid + 1

        return res


18200