LeetCode/kt/minimum-number-of-removals-to-make-mountain-array.kt

class Solution {
    private fun longestIncreasing(nums: IntArray): IntArray {
        val found =
            IntArray(nums.size) {
                1
            }

        nums.indices
            .flatMap { i ->
                (0..i - 1)
                    .reversed()
                    .map { j -> i to j }
            }
            .filter { (i, j) -> nums[i] > nums[j] }
            .forEach { (i, j) ->
                found[i] = listOf(found[i], 1 + found[j]).max()
            }

        return found
    }

    fun minimumMountainRemovals(nums: IntArray): Int {
        val increasing = longestIncreasing(nums)

        nums.reverse()
        val decreasing = longestIncreasing(nums)
        decreasing.reverse()

        return increasing
            .zip(decreasing)
            .filter { (l, r) ->
                l > 1 && r > 1
            }
            .minOf { (l, r) ->
                nums.size - l - r + 1
            } ?: nums.size
    }
}