Split Array Largest Sum LeetCode Solution

Here, We see Split Array Largest Sum LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Problem Statement

Given an integer array `nums` and an integer `k`, split `nums` into `k` non-empty subarrays such that the largest sum of any subarray is minimized.

Return the minimized largest sum of the split.

subarray is a contiguous part of the array.

Example 1:
Input: nums = [7,2,5,10,8], k = 2
Output: 18
Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.

Example 2:
Input: nums = [1,2,3,4,5], k = 2
Output: 9
Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.

Split Array Largest Sum LeetCode SolutionC++

``````class Solution {
public:
int splitArray(vector<int>& nums, int k) {
int l=0,r=0,n=nums.size();
for(int i=0;i<n;++i) l=max(l,nums[i]), r+=nums[i];
int mid=0,ans=0;
while(l<=r){
mid=(l+r)/2;
int count=0,tempsum=0;
for(int i=0;i<n;++i){
if(tempsum+nums[i]<=mid) tempsum+=nums[i];
else count++,tempsum=nums[i];
}
count++;
if(count<=k) r=mid-1, ans=mid;
else l=mid+1;
}
return ans;
}
};```Code language: PHP (php)```

Split Array Largest Sum LeetCode SolutionJava

``````class Solution {
int[] nums;
public int splitArray(int[] nums, int k) {
this.nums = nums;
int low = 0, high = 0, min = Integer.MAX_VALUE;
for(int i=0;i<nums.length;i++){
low = Math.max(low, nums[i]);
high += nums[i];
}
while(low <= high) {
int mid = (low + high) / 2;
if(required_no_of_chunks(mid, k)){
min = Math.min(min, mid);
high = mid - 1;
}
else low = mid + 1;
}
return min;
}

private boolean required_no_of_chunks(int mid, int k){
int chunks = 0, i=0;
while(i < nums.length){
int val = 0;
while(i < nums.length && nums[i] + val <= mid) val += nums[i++];
chunks++;
}
return chunks <= k;
}
}```Code language: JavaScript (javascript)```

Split Array Largest Sum LeetCode SolutionJavaScript

``````var splitArray = function(nums, k) {
let n=nums.length;
let low=Math.max(...nums)
let high=nums.reduce((acc,curr)=>{
return acc+curr
},0)
while(low<=high)
{
let mid=Math.floor((low+high)/2)
let sum=LargestSum(nums,mid)
if(sum>k)
{
low=mid+1
}
else
{
high=mid-1
}
}
return low
};
const LargestSum=(nums,mid)=>{
let n=nums.length;
let count=1;
let array=0;
for(let i=0;i<n;i++)
{
if(array+nums[i]<=mid)
{
array+=nums[i]
}
else
{
count++;
array=nums[i]
}
}
return count
}```Code language: JavaScript (javascript)```

Split Array Largest Sum SolutionPython

``````class Solution(object):
def splitArray(self, nums, k):
lo, hi = max(nums), sum(nums)
while lo < hi:
mid = (lo+hi)//2
tot, cnt = 0, 1
for num in nums:
if tot+num<=mid:
tot += num
else:
tot = num
cnt += 1
if cnt>k: lo = mid+1
else: hi = mid
return hi  ``````
Scroll to Top