Java DP O(m*n^2) solution


  • 0
    D
    public class Solution {
        public int splitArray(int[] nums, int m) {
            if (nums == null || nums.length == 0 || m < 1 || m > nums.length) {
                return 0;
            }
            int n = nums.length;
            int[][] segSum = new int[n][n];
            for (int jminusi = 0; jminusi < n; jminusi++) {
                for (int i = 0, j = i + jminusi; j < n; i++, j = i + jminusi) {
                    segSum[i][j] = nums[i] + (jminusi == 0 ? 0 : segSum[i + 1][j]);
                }
            }
            Integer[][] dp = new Integer[n][m + 1];
            for (int i = n - 1; i >= 0; i--) {
                for (int j = 1; j <= m; j++) {
                    if (j > n - i) {
                        continue;
                    }
                    if (j == 1) {
                        dp[i][j] = segSum[i][n - 1];
                        continue;
                    }
                    for (int s = i; s < n - 1; s++) {
                        Integer candidate = dp[s + 1][j - 1] == null ? null : Math.max(segSum[i][s], dp[s + 1][j - 1]);
                        dp[i][j] = dp[i][j] == null ? candidate : (candidate == null ? dp[i][j] : Math.min(dp[i][j], candidate));
                    }
                }
            }
            return dp[0][m];
        }
    }
    

Log in to reply
 

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