Hard
You are given an integer array planks, where planks[i] represents the height of the ith wooden plank. Each plank has a width of 1 unit.
You want to build a fence consisting of planks that all have the same height.
You may either use a plank as is, or combine exactly two distinct original planks into a single plank whose height equals the sum of their heights. Each original plank can be used at most once, and not all original planks need to be used.
Return the maximum possible width of the fence that can be built.
Example 1:
Input: planks = [1,3,2,5,7,5,4,2,1]
Output: 4
Explanation:
We can have four planks of height 5.
planks[3] = 5planks[5] = 5planks[0] + planks[6] = 1 + 4 = 5planks[1] + planks[2] = 3 + 2 = 5Hence, the maximum width is 4.
Example 2:
Input: planks = [2,3,7]
Output: 1
Explanation:
Constraints:
1 <= planks.length <= 10001 <= planks[i] <= 109import kotlin.math.max
class Solution {
fun maximumWidth(planks: IntArray): Int {
val freqMap: MutableMap<Int, Int> = HashMap<Int, Int>()
for (plank in planks) {
freqMap.merge(plank, 1) { a: Int, b: Int -> Integer.sum(a, b) }
}
val n = freqMap.size
var i = 0
val nums = IntArray(n)
val freq = IntArray(n)
for ((key, value) in freqMap) {
nums[i] = key
freq[i++] = value
}
return getMax(n, nums, freq)
}
companion object {
private fun getMax(n: Int, nums: IntArray, freq: IntArray): Int {
val fence: MutableMap<Int, Int> = HashMap<Int, Int>(n * n)
var max = 1
for (right in 0..<n) {
val curr = nums[right]
val count = freq[right]
max = max(
max,
fence.merge(curr, count) { a: Int?, b: Int? -> Integer.sum(a!!, b!!) }!!,
)
if (count > 1) {
max = max(
max,
fence.merge(
curr shl 1,
count shr 1,
) { a: Int?, b: Int? -> Integer.sum(a!!, b!!) }!!,
)
}
for (left in right + 1..<n) {
max = max(
max,
fence.merge(
curr + nums[left],
kotlin.math.min(count, freq[left]),
) { a: Int?, b: Int? -> Integer.sum(a!!, b!!) }!!,
)
}
}
return max
}
}
}