Java DP with Binary Search


  • 0
    H

    Similar to the other DP solutions, but use binary search to find the last cut. Time complexity: O(nmlog(n)).

    public class Solution {
        public int splitArray(int[] nums, int m) {
            int n = nums.length;
            int[] min_split = new int [n];
            int[] psum = null;
            // m = 1
            min_split[0] = nums[0];
            for (int i = 1; i < n; i++) min_split[i] = min_split[i-1]+nums[i];
            psum = Arrays.copyOf(min_split, n);
            // m = 2...m
            for (int k = 2; k <= m; k++) {
                for (int i = n-1; i >= k-1; i--) {
                    min_split[i] = bsearch(min_split, psum, k-1, i);
                }
            }
            return min_split[n-1];
        }
        int bsearch(int[] left, int[] psum, int L, int R) {
            int l = L, r = R;
            while (l < r) {
                int m = l + (r-l)/2;
                if (left[m-1] < psum[R]-psum[m-1]) l = m+1;
                else r = m;
            }
            int res = Math.max(left[l-1], psum[R]-psum[l-1]);
            if (l > L) res = Math.min(Math.max(left[l-2], psum[R]-psum[l-2]), res);
            return res;
        }
    }
    

Log in to reply
 

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