Split Array - Largest Sum
Binary Search on Answers DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Given an integer array A of size N and an integer K, split the array A into K non-empty contiguous subarrays such that the largest sum among the subarrays is minimized. Return the minimized largest sum of the split., Arrays, Subarray, Binary Search, Brute Force, Time Complexity, Space Complexity, Loops, Conditional Statements, brute force, greedy algorithm, array partitioning, subarray algorithms, binary search, time complexity analysis, Array Partitioning.
Problem Statement Given an integer array A of size N and an integer K. Your task is to split the array A into K non empty contiguous subarrays such that the largest sum of any subarray among the K subarrays is minimized. Return this minimized largest sum. A subarray is a contiguous part of the array. Input Specification The first line contains two integers, N and K, separated by a space. The second line contains N integers, the elements of array A, separated by spaces. Output Specification Return a single integer representing the minimized largest sum of the split. Examples Example 1: Input: 5 3 1 2 3 4 5 Output: 6 Explanation: There are many ways to split the array into 3 consecutive subarrays. The best way to do this is to split the array into [1, 2, 3], [4], and [5], where the largest sum among the three subarrays is 6. Example 2: Input: 3 3 3 5 1 Output: 5 Explanation: There is only one way to split the array into 3 subarrays, i.e., [3], [5], and [1]. The largest sum among these subarrays is 5. Difficulty Hard