class Solution {
    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        int[] cs = new int[n+1];

        cs[0] = 0;
        for (int i = 1; i <= n; i++)
            cs[i] = cs[i - 1] + nums[i-1];

        //System.out.println(Arrays.toString(cs));
        int[][] memo = new int[n+1][m+1];
        return search(0, m, 0, n, cs, memo);
    }

    private int search(int from, int m, int largest, int n, int[] cs, int[][] memo) {
        System.out.println("from=" + from + " m=" + m + " largest=" + largest);
        if (memo[from][m] != 0) {
            System.out.println("Return from memo " + memo[from][m] + " for " + from + " " + m);
            return memo[from][m];
        }

        if (m == 1) {
            largest = Math.max(largest, cs[n] - cs[from]);
            memo[from][m] = largest;
            System.out.println("Return " + largest + " for " + from + " " + m);
            return largest;
        }

        int minLargest = Integer.MAX_VALUE;
        for (int split = from + 1; split <= n - m + 1; split++) {
            int nextLargest = Math.max(largest, cs[split] - cs[from]);
            System.out.println("Try split at " + split + " with " + nextLargest);
            int res = search(split, m-1, nextLargest, n, cs, memo);
            minLargest = Math.min(minLargest, Math.max(nextLargest, res));
        }

        memo[from][m] = minLargest;
        System.out.println("Return " + minLargest + " for " + from + " " + m);
        return minLargest;
    }
}