# Leetcode Split Array Largest Sum problem solution

In this Leetcode Split Array Largest Sum problem solution, You are given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

## Problem solution in Python.

```class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
dp = [[float("inf") for _ in range(len(nums))] for _ in range(m)]
dp[0][0] = nums[0]
for j in range(1, len(nums)):
dp[0][j] = dp[0][j-1] + nums[j]

for i in range(1,m):
for j in range(i, len(nums)):
dp[i][j] = min([max(dp[i-1][k],dp[0][j]-dp[0][k]) for k in range(i-1, j)])
return dp[-1][-1]
```

## Problem solution in Java.

```class Solution {
public int splitArray(int[] nums, int m) {
int low = IntStream.of(nums).max().orElse(0);
int high = IntStream.of(nums).sum();
while (low < high) {
int mid = low + (high - low) / 2;
if (split(nums, mid) > m) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}

private int split(int[] nums, int sum) {
int ret = 1;
int currentSum = 0;
for (int i = 0; i < nums.length; i++) {
if (currentSum + nums[i] > sum) {
ret++;
currentSum = 0;
}
currentSum += nums[i];
}
return ret;
}
}
```

## Problem solution in C++.

```bool can_split(vector<int> &nums,int m,long long int sum)
{
long long int cnt=1,cnt_sum=0;
for (int i = 0; i <nums.size() ; ++i) {
cnt_sum+=nums[i];
if(cnt_sum>sum)
{
cnt_sum=nums[i];
++cnt;
if (cnt>m) return false;
}
}
return true;
}
int splitArray(vector<int>& nums, int m)
{
long long left=*max_element(nums.begin(),nums.end());
long long right=accumulate(nums.begin(),nums.end(),0ll);
while(left<right)
{
long long mid=(left+right)>>1;
if(can_split(nums,m,mid)) right=mid;
else left=mid+1;
}
return left;

}
```