Split Array Largest Sum

hard

Acceptance: 44%

Binary SearchDynamic Programming

Given an integer array and a number k, divide the array into exactly k contiguous segments (each non-empty). Among all possible divisions, minimize the largest segment sum. Return that minimized value.

Examples

Example 1:

Input:nums = [2,3,1,2,4,3], k = 3

Output:6

Explanation: Splitting as [2,3,1],[2,4],[3] gives segment sums 6,6,3. The largest is 6, which is optimal.

Example 2:

Input:nums = [1,4,4], k = 3

Output:4

Explanation: Each element is its own segment, so the largest sum is 4.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Split Array Largest Sum

Examples

Hints

Related Problems