Simple Java DP solution


  • 0
    S

    Naive iterative DP solution. Brute Force + Memo table

    class Solution {
        public int splitArray(int[] nums, int m) {
            int n = nums.length;
            long[] sum = new long[n + 1];
            for(int i = 0; i < nums.length; i++) {
                sum[i + 1] = sum[i] + nums[i];
            }
            int[][] table = new int[n + 1][m];
            for(int i = 0; i < n + 1; i++) {
                table[i][0] = (int) (sum[n] - sum[i]);
            }
            for(int j = 1; j < m; j++) {
                for(int i = n; i >= 0; i--) {
                    table[i][j] = Integer.MAX_VALUE;
                    for(int k = i + 1; k < n + 1; k++) {
                        table[i][j] = (int)Math.min(Math.max(sum[k] - sum[i], table[k][j-1]), table[i][j]);
                    }
                }
            }
            return table[0][m-1];
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.