Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

65. Split Array Largest Sum

HardDay 19 of 60Binary Search

Given an array nums of non-negative integers and an integer k, split nums into exactly k non-empty contiguous subarrays. Among all possible splits, minimise the largest subarray sum, and return that minimised largest sum.

Example 1
Input: nums = [7,2,5,10,8], k = 2
Output: 18
Split as [7,2,5] and [10,8]: the larger sum is 18, the best possible.
Example 2
Input: nums = [1,2,3,4,5], k = 2
Output: 9
[1,2,3] and [4,5].
Constraints
  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 10^6
  • 1 <= k <= min(50, nums.length)
Hints
Frequently asked at: Google, Amazon, Flipkart, D. E. Shaw
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min