LC410. Split Array Largest Sum

Given an array 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.

Note: If n is the length of array, assume the following constraints are satisfied:

1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)

Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

求将一个array分成m部分，每部分和的最大值是多少。

我想想，对于每个可能位置求一下，然后把所有结果加起来？时间复杂度爆炸了呀…

BinarySearch Java

拜倒在了discuss大神的答案下。对于这个array，subarray和的最大值的最大值和最小值就是max(items in Array)和sum(Array). 然后利用BinaySearch，二分查找这个区间内的值，使得每个subarray的max小于等于mid，如果可以成功，证明当前值可以增大试试，向右边搜索；否则证明当前值太小了，只能将subarray再分开，就像左边搜索。

public class Solution {
    public int splitArray(int[] nums, int m) {
        long max = 0, sum = 0;
        for(int n: nums){
            max = (long)Math.max(max, n);
            sum += n;
        }
        // for each m for nums, the max of res must be sum of array, min should be max in array
        // binary search for each other number between max and sum
        // when valid reduce mid, else increase mid
        long l = max, r = sum;
        while(l <= r){
            long mid = l + (r - l)/2;
            if(valid(mid, nums, m)){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        } // while
        return (int)l;
    }
    
    private boolean valid(long mid, int[] nums, int m){
        int count = 1;
        long sum = 0;
        for(int n: nums){
            sum += n;
            if(sum > mid){
                sum = n;
                count++;
                if(count > m)   return false;
            }
        } // for
        return true;
    }
}

O(nlgn)?

FEATURED TAGS

Java Hashset Linkedhashset BFS Array DFS Hashmap Design ICC DP Stack Python Database BinarySearch ArrayList SegmentTree BIT TopologicalSort Bit BST TreeSet TreeMap Trie String LinkedList KMP D&C Greedy Math Backtracking Tree UnionFind TwoPointers C/C++ GC Web Sort Graph DS DL PP ML Sampling Minimax Heap

LC410. Split Array Largest Sum

CATALOG

FEATURED TAGS