<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 __init__(self):
        self.memoized: Dict[Tuple[int, int, int], int] = {}

    def get_memoized(self, k: int, idx: int, holdover: int) -> Optional[int]:
        if holdover > 0:
            return None
        return self.memoized.get((k, idx))

    def set_memoized(self, k: int, idx: int, holdover: int, value: int):
        if holdover == 0:
            self.memoized[(k, idx)] = value

    def split_array_memoized(
        self,
        nums: List[int],
        k: int,
        idx: int,
        holdover: int,
    ) -> int:
        memoized_result = self.get_memoized(k, idx, holdover)
        if memoized_result is not None:
            return memoized_result

        # print(f"k:{k} idx:{idx} val:{nums[idx]} hold:{holdover}")

        # if we split into a single array, the value is the sum
        if k == 1:
            result = sum(nums[idx:]) + holdover
            self.set_memoized(k, idx, holdover, result)
            # print(f"result:{result}")
            return result
        
        # if the number of arrays is equal to the number of elements
        # it can be shortcutted
        if k == len(nums) - idx:
            result = max([holdover + nums[idx]] + nums[idx+1:])
            self.set_memoized(k, idx, holdover, result)
            # print(f"result:{result}")
            return result

        # we can either split here, or keep going
        # case 1: split
        curr_subarray_value = holdover + nums[idx]
        next_idx = idx + 1
        next_k = k - 1
        other_subarray_value = self.split_array_memoized(
            nums=nums,
            k=next_k,
            idx=next_idx,
            holdover=0,
        )
        # print(f"curr:{curr_subarray_value}, other:{other_subarray_value}")
        split_result = max(curr_subarray_value, other_subarray_value)

        # case 2: do not split
        next_holdover = holdover + nums[idx]
        unsplit_result = self.split_array_memoized(
            nums=nums,
            k=k,
            idx=next_idx,
            holdover=next_holdover,
        )
        
        result = min(split_result, unsplit_result)
        self.set_memoized(k, idx, holdover, result)
        # print(f"r1:{split_result} r2:{unsplit_result} result:{result}")
        return result
        

    def splitArray(self, nums: List[int], k: int) -> int:
        self.memoized = {}
        
        return self.split_array_memoized(
            nums=nums,
            k=k,
            idx=0,
            holdover=0,
        )
25800