Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings
This repository was archived by the owner on Nov 25, 2022. It is now read-only.

Latest commit

 

History

History
History
44 lines (37 loc) · 1.26 KB
/

SplitArray.java

File metadata and controls

44 lines (37 loc) · 1.26 KB
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// https://leetcode.com/problems/split-array-largest-sum/
public class SplitArray {
public static void main(String[] args) {
}
public static int splitArray(int[] nums, int m) {
int start = 0;
int end = 0;
for (int i = 0; i < nums.length; i++) {
start = Math.max(start, nums[i]); // in the end of the loop this will contain the max item of the array
end += nums[i];
}
// binary search
while (start < end) {
// try for the middle as potential ans
int mid = start + (end - start) / 2;
// calculate how many pieces you can divide this in with this max sum
int sum = 0;
int pieces = 1;
for (int num : nums) {
if (sum + num > mid) {
// you cannot add this in this subarray, make new one
// say you add this num in new subarray, then sum = num
sum = num;
pieces++;
} else {
sum += num;
}
}
if (pieces > m) {
start = mid + 1;
} else {
end = mid;
}
}
return end; // here start == end
}
}
Morty Proxy This is a proxified and sanitized view of the page, visit original site.