Today I have done leetcode's October LeetCoding Challenge with cpp.

October LeetCoding Challenge 30

Description

Minimum Number of Removals to Make Mountain Array

You may recall that an array arr is a mountain array if and only if:

• arr.length >= 3
• There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array nums​​​, return the minimum number of elements to remove to make nums​​​ a mountain array.

Example 1:

Input: nums = [1,3,1]
Output: 0
Explanation: The array itself is a mountain array so we do not need to remove any elements.

Example 2:

Input: nums = [2,1,1,5,6,2,3,1]
Output: 3
Explanation: One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].

Constraints:

• 3 <= nums.length <= 1000
• 1 <= nums[i] <= 109
• It is guaranteed that you can make a mountain array out of nums.

Solution

class Solution {
public:
  int minimumMountainRemovals(vector<int>& nums) {
    int len = nums.size();
    vector<int> upDP(len, 1);
    vector<int> downDP(len, 0);

    int maxMountainLen = 0;
    for(int i = 1; i < len; ++i) {
      for(int j = 0; j < i; ++j) {
        if(nums[i] > nums[j]) {
          upDP[i] = max(upDP[i], upDP[j] + 1);
        } else if(nums[i] < nums[j]) {
          if(upDP[j] > 1) downDP[i] = max(downDP[i], upDP[j] + 1);
          if(downDP[j] > 1) downDP[i] = max(downDP[i], downDP[j] + 1);
        }
      }
      maxMountainLen = max(maxMountainLen, downDP[i]);
    }
    return len - maxMountainLen;
  }
};