Table of Contents

# Split Array Largest Sum – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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.

**Example 1:**

Input:nums = [7,2,5,10,8], m = 2Output:18Explanation: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], m = 2Output:9

**Example 3:**

Input:nums = [1,4,4], m = 3Output:4

**Constraints:**

`1 <= nums.length <= 1000`

`0 <= nums[i] <= 10`

^{6}`1 <= m <= min(50, nums.length)`

# C++ Split Array Largest Sum LeetCode Solution

```
``````
int splitArray(vector<int>& nums, int m) {
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<=m) r=mid-1, ans=mid;
else l=mid+1;
}
return ans;
}
```

# Java Split Array Largest Sum LeetCode Solution

```
``````
class Solution {
int[] nums;
public int splitArray(int[] nums, int m) {
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, m)){
min = Math.min(min, mid);
high = mid - 1;
}
else low = mid + 1;
}
return min;
}
private boolean required_no_of_chunks(int mid, int m){
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 <= m;
}
}
```

# Python 3 Split Array Largest Sum LeetCode Solution

```
``````
class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
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>m: lo = mid+1
else: hi = mid
return hi
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1