altay9
commented
3 years ago 410. Split Array Largest Sum
The dynamic programming approach here takes use of
the fact that splitting operations do not affect other parts of the array.At some indexj, having split the array into 3 parts would result in the maximum sum equal to the maximum of: sum of elements up toj, maximum sum of the array afterjwhen split into 2. Such an approach generalizes pretty easily. It is less efficient than binary searching though.
So, it is good to note these properties again:
1011. Capacity To Ship Packages Within D Days
Problem: https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/ In this problem, it's obvious that we are searching for something. The capacity of the ship is some value in some interval. If we guess a capacity that results in us shipping in less than d days, then we should try to go with a lower capacity. If we guess a capacity that results in us shipping in too many days, then we should increase the capacity to include weights together. It should now be somewhat apparent that we can do this using binary searching. We can pick some capacity, try to count if weights can be loaded according to it, and go lower or higher depending on the result.
410. Split Array Largest Sum
Problem: https://leetcode.com/problems/split-array-largest-sum/ There are 2 ways of approaching this problem. The first one is binary searching in a way similar to the one above. If a target some results in the array being split in more than m parts, that means that the target is too high and we should go lower. If it results in array being split in too many parts, that means that it is too low Nd the target must be higher. We eventually find a value that splits the array in m part and is the minimum of all such values.
The dynamic programming approach here takes use of the fact that splitting operations do not affect other parts of the array.At some index
j, having split the array into 3 parts would result in the maximum sum equal to the maximum of: sum of elements up toj, maximum sum of the array afterjwhen split into 2. Such an approach generalizes pretty easily. It is less efficient than binary searching though.