Minimum Number of Removals to Make Mountain Array LeetCode solution in Python

1
class Solution:
2
    def minimumMountainRemovals(self, nums: List[int]) -> int:
3
        n = len(nums)
4
        inc = [0] * n
5
        dec = [0] * n
6

7
        #  Longest Increasing Subsequence
8
        for i in range(1, n):
9
            for j in range(0, i):
10
                if nums[i] > nums[j]:
11
                    inc[i] = max(inc[i], inc[j] + 1)
12

13
        #  Longest Decreasing Subsequence
14
        for i in range(n - 2, -1, -1):
15
            for j in range(n - 1, i, -1):
16
                if nums[i] > nums[j]:
17
                    dec[i] = max(dec[i], dec[j] + 1)
18

19
        # Final calculation
20
        res = 0
21
        for i in range(0, n):
22
            if inc[i] > 0 and dec[i] > 0:
23
                res = max(res, inc[i] + dec[i])
24

25
        # Final conclusion
26
        return n - res - 1