<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], m: int) -> int:
#         dp = {}
#         def dfs(i, m):
#             if m == 1:
#                 return sum(nums[i:])
#             if (i,m) in dp:
#                 return dp[(i,m)]
#             cur_sum, res = 0, float("inf")
#             for j in range(i, len(nums)-m-1):
#                 cur_sum += nums[j]
#                 max_sum = max(cur_sum, dfs(j+1,m-1))
#                 res = min(res, max_sum)
#                 if cur_sum > res:
#                     break
                
#             dp[(i,m)] = res
#             return res
#         return dfs(0, m)
from typing import List
import sys

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        n = len(nums)
        if n == m:
            return max(nums)

        # Prefix sums to quickly calculate subarray sums
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + nums[i]
        
        # Function to get the sum of a subarray
        def get_sum(start: int, end: int) -> int:
            return prefix_sum[end + 1] - prefix_sum[start]
        
        # DP cache
        dp = {}
        
        def dfs(i: int, m: int) -> int:
            if m == 1:
                return get_sum(i, n - 1)
            if (i, m) in dp:
                return dp[(i, m)]
            
            cur_sum, res = 0, float("inf")
            for j in range(i, n - m + 1):
                cur_sum += nums[j]
                max_sum = max(cur_sum, dfs(j + 1, m - 1))
                res = min(res, max_sum)
                if cur_sum >= res:
                    break
            
            dp[(i, m)] = res
            return res
        
        return dfs(0, m)

23500