Last Updated: 7 Feb, 2023

Largest Subarray Sum Minimized

Hard

Solve now

Problem statement

Given an integer array ‘A’ of size ‘N’ and an integer ‘K'.

Split the array ‘A’ into ‘K’ non-empty subarrays such that the largest sum of any subarray is minimized.

Your task is to return the minimized largest sum of the split.

A subarray is a contiguous part of the array.

Example:

Input: ‘N’ = 5, ‘A’ = [1, 2, 3, 4, 5], ‘K’ = 3

Output: 6

Explanation: There are many ways to split the array ‘A’ into K consecutive subarrays. The best way to do this is to split the array ‘A’ into [1, 2, 3], [4], and [5], where the largest sum among the three subarrays is only 6.

Input Format

The first line contains one integer, ‘N’, denoting the size of the array ‘A’.

The second line contains ‘N’ integers denoting the elements of the array ‘A’.

The third line contains one integer, ‘K’, denoting the number in which array ‘A’ should be split.

Output format:

Return the minimized largest sum of the split.

Note:-

You don't need to print anything. Just implement the given function.

Solve now

Approaches

01 Approach

We will use Binary Search here. Binary Search will minimize the maximized sum we can get from the array ‘A’ after breaking it into ‘K’ consecutive subarrays.

We will keep two variables, ‘s’ and ‘e’, initially assigned to ‘1’ and ‘1e9’, respectively. When applying the binary search algorithm, suppose we find the ‘mid’ as ‘(s + e) / 2’. Now, We will determine whether it is possible to array ‘A’ into subarrays such that the sum of each subarray is less than or equal to ‘mid’. Suppose, satisfying this condition, the number of subarrays that will be generated is equal to ‘num’. If ‘num’ is equal to ‘K’, then the answer will be ‘mid’, and to get a smaller answer, we will do ‘e’ = ‘mid - 1’. If ‘num’ is less than ‘K’, we have to increase the number of subarrays that will be generated, so for that, we will do ‘e’ = mid - 1.

Otherwise, We would do ‘s’ = mid + 1, which means ‘num’ is greater than ‘K’, so to decrease the number of subarrays that will be generated, we would increase s, or ‘s’ = mid + 1.

The steps are as follows:-

// Function to check whether we can split the array into subarrays with maximum sum ‘mid’
function isValid(int[] a, int k, int mid):

Initialize a variable ‘sum’ and assign it to ‘0’.
Initialize a variable ‘cnt’ ans assign it to ‘0’.
Iterate over the array ‘a’ using a variable ‘i’:
Initialize a variable ‘cur’ and assign it to the current array element ‘a’.
If cur > mid:
Return false.
If sum + a[i] > mid:
Increment ‘cnt’ by 1.
Initialize ‘sum’ by ‘cur’.
If cnt >= m:
Return false.
Else:
Add ‘cur’ to ‘sum’.
Return true.

// Function to find the minimized largest sum of the split.

function largestSubarraySumMinimized(int n, int[] a, int k):

Int n is the number of elements in the array ‘a’.
Declare two variables, ‘s’ and ‘e’, initially assigned to ‘1’ and ‘1e9’, respectively.
Initialize a variable ‘ans’, which will store our final answer.
While s <= e:
Initialize a variable ‘mid’ and assign it to ‘(s + e) / 2’.
Initialize a variable ‘ok’ and assign it to isValid(a, k, mid).
If ok == true:
Assign ‘mid’ to ‘ans’.
Assign ‘e’ to ‘mid - 1’.
Else:
Assign ‘s’ to ‘mid + 1’.
Return ‘ans’.

Solve now

Largest Subarray Sum Minimized

Problem statement

Given an integer array ‘A’ of size ‘N’ and an integer ‘K'.

Split the array ‘A’ into ‘K’ non-empty subarrays such that the largest sum of any subarray is minimized.

Your task is to return the minimized largest sum of the split.

A subarray is a contiguous part of the array.

Example:

Input Format

Output format:

Note:-

Approaches

01 Approach

The steps are as follows:-

// Function to check whether we can split the array into subarrays with maximum sum ‘mid’function isValid(int[] a, int k, int mid):

// Function to check whether we can split the array into subarrays with maximum sum ‘mid’
function isValid(int[] a, int k, int mid):