410. Split Array Largest Sum
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.
A 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.
Constraints:
1 <= nums.length <= 10000 <= nums[i] <= 1061 <= k <= min(50, nums.length)
Solution:
DFS:
class Solution {
public int splitArray(int[] nums, int k) {
int n = nums.length;
// 计算前缀和，用于快速求任意子数组和
int[] prefixSum = new int[n + 1];
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
// 调用DFS函数
return dfs(nums, prefixSum, 0, k);
}
// DFS函数，返回从start位置开始，将剩余数组分成k段的最小最大子数组和
private int dfs(int[] nums, int[] prefixSum, int start, int k) {
int n = nums.length;
// 当只剩下1段时，直接返回从start到数组末尾的和
if (k == 1) {
return prefixSum[n] - prefixSum[start];
}
int result = Integer.MAX_VALUE;
// 尝试从start到n-k位置的所有分割点
for (int i = start; i <= n - k; i++) {
// 计算从start到i的子数组和
int currentSum = prefixSum[i + 1] - prefixSum[start];
// 递归处理剩余的部分，分成k-1段
int nextSplit = dfs(nums, prefixSum, i + 1, k - 1);
// 取当前子数组和与剩余部分的最大值，确保每段的最大和尽可能小
result = Math.min(result, Math.max(currentSum, nextSplit));
// 剪枝：如果当前子数组和已经大于result，可以提前结束
if (currentSum >= result) {
break;
}
}
return result;
}
}
// TC: O(n^k) TLE
// SC: O(n)
// level: 进行了第几次分割
// branch: 在每一层表示我们在该层级尝试不同分割
// 每个分支表示我们从当前位置 start 到某个位置 p 进行分割后的情况。不同的 p 代表不同的分割选择。
graph TD;
A["dfs(0, 2)"] --> B1["Split at 0: [7], dfs(1, 1)"];
A --> B2["Split at 1: [7, 2], dfs(2, 1)"];
A --> B3["Split at 2: [7, 2, 5], dfs(3, 1)"];
A --> B4["Split at 3: [7, 2, 5, 10], dfs(4, 1)"];
B1 --> C1["Remaining: [2, 5, 10, 8], Sum = 25"];
B2 --> C2["Remaining: [5, 10, 8], Sum = 23"];
B3 --> C3["Remaining: [10, 8], Sum = 18"];
B4 --> C4["Remaining: [8], Sum = 8"];
A --> D["Final Result: Min(25, 23, 18, 24) = 18"];
DFS + Memo
class Solution {
public int splitArray(int[] nums, int k) {
int n = nums.length;
int[] prefixSum = new int[n + 1]; // 前缀和数组，用于快速计算子数组的和
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
// 记忆化数组，dp[i][k] 表示从位置 i 开始，将剩余的元素分成 k 段的最优解
int[][] memo = new int[n][k + 1];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
// 调用DFS函数，从位置0开始，划分成k段
return dfs(nums, prefixSum, memo, 0, k);
}
// DFS函数，返回从start位置开始，划分成k段的最小最大子数组和
private int dfs(int[] nums, int[] prefixSum, int[][] memo, int start, int k) {
int n = nums.length;
// 如果只剩下1段，那就返回从start到末尾的子数组的和
if (k == 1) {
return prefixSum[n] - prefixSum[start];
}
// 如果这个状态已经计算过，直接返回记忆化结果
if (memo[start][k] != -1) {
return memo[start][k];
}
int result = Integer.MAX_VALUE;
// 尝试所有可能的分割点
for (int i = start; i <= n - k; i++) {
// 计算当前子数组和
int currentSum = prefixSum[i + 1] - prefixSum[start];
// 递归计算剩余部分的最优解
int nextSplit = dfs(nums, prefixSum, memo, i + 1, k - 1);
// 取当前子数组和与剩余部分的最优解中的最大值，保证子数组和的最大值最小化
int maxSum = Math.max(currentSum, nextSplit);
// 更新最优解
result = Math.min(result, maxSum);
// 剪枝：如果当前子数组的和已经大于等于result，就可以提前结束
if (currentSum >= result) {
break;
}
}
// 记忆化结果
memo[start][k] = result;
return result;
}
}
graph TD;
A["Start dfs(0, 2)"] --> B1["dfs(1, 1) = 25"];
A --> B2["dfs(2, 1) = 23"];
A --> B3["dfs(3, 1) = 18"];
A --> B4["dfs(4, 1) = 8"];
B1 --> C1["Split at 0: max(7, 25) = 25"];
B2 --> C2["Split at 1: max(9, 23) = 23"];
B3 --> C3["Split at 2: max(14, 18) = 18"];
B4 --> C4["Split at 3: max(24, 8) = 24"];
C1 --> D1["Result: 25"];
C2 --> D2["Result: 23"];
C3 --> D3["Result: 18"];
C4 --> D4["Result: 24"];
A --> E["Final Result: Min(25, 23, 18, 24) = 18"];
class Solution {
public int splitArray(int[] nums, int k) {
int left = 0;
int right = 0;
for (int num : nums){
left = Math.max(left, num);
right = right + num;
}
while(left < right){
int mid = left + (right - left) /2;
if (canSplit(nums, k, mid)){
right = mid;
}else{
left = mid + 1;
}
}
return left;
}
private boolean canSplit(int[] nums, int k, int target){
int count = 1;
int currentSum = 0;
for (int num : nums){
currentSum = currentSum + num;
if (currentSum > target){
count++;
currentSum = num;
}
if (count > k){
return false;
}
}
return true;
}
}
// TC: O(nlog(sum - max))
// SC: O(1)
??? $$ dp[i][j] = min_{p<j}(max(dp[i-1][p], sum \ of \ nums \ from \ p + 1 \ to \ j )) $$
class Solution {
public int splitArray(int[] nums, int k) {
int n = nums.length; // n 5
int[] prefixSum = new int[n + 1];
for (int i = 0; i < n; i++){
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
/*
0 1 2 3 4 5
7 2 5 10 8
0 7 9 14 24 32
k = 2
0 1 2 3 4 5
7 2 5 10 8
0 - - - - - -
1 0 7 9 14 24 32
2 - - 7 - - - i = 2
p
j
*/
int[][] dp = new int[k + 1][n + 1];
// dp[i][j]: i represents the number of subarrays used so far(splits)
// j: represents the first j elements of the array being considered.
// dp[i][j] will store the minimum possible largest sum for splitting the
// first j elements into exactly i subarrays.
// fill dp array with a large value (infinity)
for (int i = 0; i <= k; i++){
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
// Base case: for one subarray, the largest sum is the the
// total sum of the first j elements
for (int j = 0; j <= n; j++){
dp[1][j] = prefixSum[j];
}
// DP transitions: Try to split into subarrays
for (int i = 2; i <= k; i++){ // i subarrays // 2
for (int j = i; j <= n; j++){ // first j elements // 2, 3
for (int p = i - 1; p < j; p++){ // consider splitting at p
dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - 1][p], prefixSum[j] - prefixSum[p])); // dp[2][2] = Math.min(dp[2][2], Math.max(dp[1][1]), prefixSum[2] - prefixSum[1])
// dp[2][2] = Math.min(-, Math.max(7, 9 - 7))
// dp[2][2] = Math.min(-, Math.max(7, 2)) == 7
// =====
// dp[2][2]
}
}
}
// The result is the minimum largest sum to split the entire array into k subarrays
return dp[k][n];
}
}
// TC: O(n^2)
// SC: O(n^2)
前缀和数组:
使用前缀和数组prefixSum来快速计算任意子数组的和. prefixSum[j] - prefixSum[p] 表示从位置p + 1到j 的子数组和.
DP状态转移:
dp[i][j]表示将前j个元素分成i段时的最小最大数组和- 对于每一段
i, 我们尝试在每一个位置p进行分割, 然后计算当前段的和从p+1到j的子数组和, 并在所有可能的p中取最小的最大值
返回结果
最终结果是dp[k][n], 它表示将整个数组分成k段时, 子数组和的最小最大值
1011. Capacity To Ship Packages Within D Days
https://www.youtube.com/watch?app=desktop&v=YUF3_eBdzsk