Split Array to Minimize Largest Sum Problem

Split Array to Minimize Largest Sum Problem — ExecCode Medium DSA Practice

Solve the Split Array to Minimize Largest Sum problem on ExecCode. Free online medium DSA practice in Searching & Sorting. Write and run code in Java, C++, Python — no signup required to run.

Problem description

You are given a non-negative integer array a and an integer k. Split the array into exactly k non-empty contiguous parts. The cost of a split is the maximum sum among those parts. Return the minimum possible cost. Use a 64-bit integer. You are given: a — non-negative integers k — number of parts Return the minimum possible largest part sum, as a 64-bit integer. Parts must be contiguous and non-empty, and there must be exactly k of them. Binary search the cost: the smallest limit that can be achieved with at most k greedy parts.

Examples

Input {'a': [7, 2, 5, 10, 8], 'k': 2}; Output 18. Input {'a': [1, 2, 3, 4, 5], 'k': 2}; Output 9. Input {'a': [1, 4, 4], 'k': 3}; Output 4

Constraints

1 <= a.length <= 1000 0 <= a[i] <= 1000000000 1 <= k <= a.length The answer fits in a signed 64-bit integer

Practice Split Array to Minimize Largest Sum free on ExecCode. Browse DSA problems, topic map, and placement guides.