<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>

from functools import cache

class Solution:
    def splitArray(self, nums: List[int], K: int) -> int:

        # [7,2,5,10,8]

        prefix_sums = [0] # [0, 7, 9, 14, 24, 32]
        total = 0
        for num in nums:
            total += num
            prefix_sums.append(total)


        @cache
        def dp(start_idx, k): # minimum largest in nums[start_idx:] using k
            if start_idx > len(nums) - 1:
                return -1
            
            if k == 1:
                end_sum = prefix_sums[len(nums)] - prefix_sums[start_idx]
                return end_sum

            best = float('inf')

            for new_start in range(start_idx + 1, len(nums)):
                current_sum = prefix_sums[new_start] - prefix_sums[start_idx]
                tail_best = dp(new_start, k - 1)
                if tail_best == -1:
                    continue
                next_max = max(tail_best, current_sum)
                best = min(next_max, best)

            if best == float('inf'):
                return -1
            return best

        return dp(0, K)

            
        
25700