-
Notifications
You must be signed in to change notification settings - Fork 1
/
Split-array.cpp
57 lines (46 loc) · 2.36 KB
/
Split-array.cpp
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
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
// Defined it as per the maximum size of array and split count
// But can be defined with the input size as well
int memo[1001][51];
int getMinimumLargestSplitSum(vector<int>& prefixSum, int currIndex, int subarrayCount) {
int n = prefixSum.size() - 1;
// We have already calculated the answer so no need to go into recursion
if (memo[currIndex][subarrayCount] != -1) {
return memo[currIndex][subarrayCount];
}
// Base Case: If there is only one subarray left, then all of the remaining numbers
// must go in the current subarray. So return the sum of the remaining numbers.
if (subarrayCount == 1) {
return memo[currIndex][subarrayCount] = prefixSum[n] - prefixSum[currIndex];
}
// Otherwise, use the recurrence relation to determine the minimum largest subarray
// sum between currIndex and the end of the array with subarrayCount subarrays remaining.
int minimumLargestSplitSum = INT_MAX;
for (int i = currIndex; i <= n - subarrayCount; i++) {
// Store the sum of the first subarray.
int firstSplitSum = prefixSum[i + 1] - prefixSum[currIndex];
// Find the maximum subarray sum for the current first split.
int largestSplitSum = max(firstSplitSum,
getMinimumLargestSplitSum(prefixSum, i + 1, subarrayCount - 1));
// Find the minimum among all possible combinations.
minimumLargestSplitSum = min(minimumLargestSplitSum, largestSplitSum);
if (firstSplitSum >= minimumLargestSplitSum) {
break;
}
}
return memo[currIndex][subarrayCount] = minimumLargestSplitSum;
}
int splitArray(vector<int>& nums, int m) {
// Marking all values to -1 so that we can differentiate
// If we have already calculated the answer or not
memset(memo, -1, sizeof(memo));
// Store the prefix sum of nums array.
int n = nums.size();
vector<int> prefixSum(n + 1, 0);
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
return getMinimumLargestSplitSum(prefixSum, 0, m);
}
};