Java - Split Array Largest Sum (Hard, LeetCode)

Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.

Write an algorithm to minimize the largest sum among these m subarrays.

 

Example 1:

Input: nums = [7,2,5,10,8], m = 2 Output: 18 Explanation: 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.

Example 2:

Input: nums = [1,2,3,4,5], m = 2 Output: 9

Example 3:

Input: nums = [1,4,4], m = 3 Output: 4

 

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 106
• 1 <= m <= min(50, nums.length)

class Solution {
    public int splitArray(int[] nums, int m) {
        int n = nums.length;
        System.out.println("n=" + n + " m="+m);

        // min largest subarray sum
        // +1, +1은 마지막 저장 장소
        int[][] f = new int[n + 1][m + 1];
        int[] sub = new int[n + 1];

        // 최대값 저장 (min largest 이므로)
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                f[i][j] = Integer.MAX_VALUE;
            }
        }

        // 앞의 nums[i]를 누적해서 더함
        for (int i = 0; i < n; i++) {
            sub[i + 1] = sub[i] + nums[i];
        }

        //DEBUG sub
        for(int i=0;i<n+1; i++) {
            System.out.println(sub[i]);
        }

        // 왜 이걸초기화 하지? invalid를 위해서
        f[0][0] = 0;
        for (int i = 1; i <= n; i++) {// 현재 배열의 번호 (right)
            for (int j = 1; j <= m; j++) {// 현재 부분집합의 번호 (1~m)
                for (int k = 0; k < i; k++) {// 현재 배열의 번호 (left)
                    // f[k][j - 1] = 현재 left(k)에서의 m번째 배열의 최대값
                    // sub[i] - sub[k] = 현재 위치(right)에서 현재 부분집합(k)의 갯수 만큼 빼기, 현재가 4라면 부분집합의 시작은 2일경우 2~4의 합
                    int val = Math.max(f[k][j - 1], sub[i] - sub[k]);

                    // val보다 기존의 저장된 값보다 작으면 저장
                    f[i][j] = Math.min(f[i][j], val);
                    System.out.println("i="+i+ " j=" +j + " k=" + k + " val=" + val + " f[i][j]="+f[i][j]);
                }
            }
        }

        // 가장 마지막에 저장해 놓음
        // n,m을 사용할수 있는 이유는 i <=n, j<= m을 했기 때문임
        return f[n][m];
    }
}