Algorithm & Data Structure - Split array
Problem Statement
Split array into some subarray with conditions. Examples:
These two problems has common array split requirement:
- Array need to split into subarrays;
- Subarrays have to be continous;
Basic approach is to insert plate between array element and split the array. For example, for the array below with 2 subarrays:
| 7 2 | 5 10 | 8 |
We could insert two plate between any two elements, and calculate the sum of each subarray and then find out the maximum sum.
DFS with memeory - Top Down
Brutal force is basiclly to search all the possibility, we can thus use DFS search method. Because subarray has to be continous, we could move insertion points one by one, and calculate the current subarray sum comparing with the maximum sum after the current point.
private int dfs(int i, int m, int[] nums, int[][] mem) {
if (i == nums.length && m == 0) return 0;
if (i == nums.length || m == 0) return Integer.MAX_VALUE;
if (mem[i][m] != -1) return mem[i][m];
int curSum = 0;
int curMax = Integer.MAX_VALUE;
for (int j = i; j < nums.length; j++) {
// sum from subarray [i...j]
curSum += nums[j];
int tmp = Math.max(curSum, dfs(j + 1, m - 1, nums, mem));
curMax = Math.min(curMax, tmp);
}
mem[i][m] = curMax;
return curMax;
}
Dynamic programming - Bottom Up
Suppose we know largest sum for \([1...i-1]\) element with \(j-1\) subarrays (of course, \(i\) need to be more than \(j\)) and all previous results. Consider how could we use this already known results to obtain largest sum for \([1....i]\) with \(j\) subarrays. There are options for us to select:
- We could combine from \([k...i]\) where \(k <= i\) to form a subarray. And we already know the largest sum of \([1...k-1]\) with \(j-1\) subarrays. So we could get the largest sum from these two results.
- We need to loop through all \(k\) between \(j\) to \(i\). So time complextity is O(n x n x m).
private int dpMethod(int[] nums, int m) {
int n = nums.length;
int [][] dp = new int[n+1][m+1];
for (int i = 1; i < n+1; i++) {
dp[i][1] = dp[i-1][1] + nums[i-1];
}
for (int j = 2; j < m+1; j++)
for (int i = j; i < n+1; i++) {
int curSum = 0;
dp[i][j] = Integer.MAX_VALUE;
// the loop inside could be changed for different condition (largest subarray sum or larget value in a subarray)
for (int k = i; k >= j; k--) {
curSum += nums[k-1];
int maxsum = Math.max(dp[k-1][j-1], curSum);
dp[i][j] = Math.min(dp[i][j], maxsum);
}
}
return dp[n][m];
}
Binary search:
This method only applies to LC 410, because we could us O(n) to check whether the array could be split to a way with certain largest sum. With this check, we could then use binary search to find the minimum largeest sum. Time complexity O(nlogn);
public int splitArray(int[] nums, int m) {
int min = 0, max = 0;
for (int num : nums) {
max += num;
min = Math.max(min, num);
}
int res = max;
//System.out.println(min + " "+max);
while (min < max) {
int mid = min + (max-min)/2;
if (isValid(nums, m, mid)) {
res = mid;
max = mid;
} else {
min = mid+1;
}
}
return res;
}
boolean isValid(int[] nums, int m, int max) {
int curSum = 0;
for (int i = 0; i < nums.length; i++) {
if (curSum + nums[i] > max) {
m--;
curSum = 0;
}
if (m < 1) return false;
curSum += nums[i];
}
return true;
}