Split Array Largest Sum
Updated
Problem statement
You are given an integer array nums and an integer k.
Split nums into exactly k parts. Each part must be a non-empty block of neighboring elements, and every element must belong to exactly one part. The parts keep the original order of the array.
The largest sum of a split is the biggest sum among its k parts. Return the smallest largest sum you can get.
Function
splitArray(nums: int[], k: int) → intExamples
Example 1
nums = [3,1,4,1,5]k = 2return = 8There are four ways to split into 2 parts:
[3] [1,4,1,5]: sums3and11, largest11.[3,1] [4,1,5]: sums4and10, largest10.[3,1,4] [1,5]: sums8and6, largest8.[3,1,4,1] [5]: sums9and5, largest9.
The smallest of these is 8.
Example 2
nums = [1,2,3]k = 1return = 6With k = 1, the whole array is one part, and its sum is 1 + 2 + 3 = 6.
Example 3
nums = [0,5,0]k = 3return = 5With k = 3, each element is its own part: [0] [5] [0]. The largest sum is 5.
Constraints
1 <= nums.length <= 10000 <= nums[i] <= 10^61 <= k <= min(50, nums.length)
More AuxoAI Online Assessment questions
Similar questions at other companies
- Split Array to Minimize the Largest SumInfosys · OAInfosys interview questions
- Split Array to Minimize the Largest SumNation with NaMo · PHONE SCREEN
- Minimize the Largest Part BeautyAdobe · PHONE SCREENAdobe interview questions
- Split Array Largest SumBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Maximum Non-Decreasing Array LengthVisa · OAVisa interview questions
- Get Minimum IncrementIBM · OAIBM interview questions
- Maximize Array Beauty After DeletionsPoint72 · OAPoint72 interview questions
- Data ReorganizationGoldman Sachs · OAGoldman Sachs interview questions
- Min Elements to Remove to Make Almost Sorted ArraySalesforce · OASalesforce interview questions
- Find Optimal LevelAmazon · OA