This approach involves finding the longest increasing subsequence (LIS) ending at each index and the longest decreasing subsequence (LDS) starting from each index. The idea is to find a peak such that the sum of the longest increasing and decreasing subsequences is maximized, and then determine how many elements need to be removed such that only the peak and the subsequences are left.
Time Complexity: O(n^2), where n is the length of the array, due to the nested loops to calculate LIS and LDS.
Space Complexity: O(n) for the LIS and LDS arrays.
1#include <vector>
2using namespace std;
3
4int minMountainRemovals(vector<int>& nums) {
5 int n = nums.size();
6 vector<int> lis(n, 1), lds(n, 1);
7
8 // Compute LIS for each index
9 for (int i = 0; i < n; ++i)
10 for (int j = 0; j < i; ++j)
11 if (nums[i] > nums[j])
12 lis[i] = max(lis[i], lis[j] + 1);
13
14 // Compute LDS for each index
15 for (int i = n - 1; i >= 0; --i)
16 for (int j = n - 1; j > i; --j)
17 if (nums[i] > nums[j])
18 lds[i] = max(lds[i], lds[j] + 1);
19
20 int maxMountain = 0;
21 for (int i = 0; i < n; ++i)
22 if (lis[i] > 1 && lds[i] > 1)
23 maxMountain = max(maxMountain, lis[i] + lds[i] - 1);
24
25 return n - maxMountain;
26}
27This C++ implementation follows the same logic as the C version. We use vectors to store the LIS and LDS values. We calculate the maximum possible mountain length and subtract it from the array's size to find the minimum number of removals required.
This method involves a greedy approach using two-pointer strategy to find potential mountain peaks. We employ two pointers to detect increasing and decreasing sequences, merging the results to form the largest mountain, iteratively removing non-peak elements.
Time Complexity: O(n^2), requiring traversal through sequences twice with nested loops.
Space Complexity: O(n) due to additional arrays retaining incremental results.
1#include <stdio.h>
2#include <string.h>
3
4int minMountainRemovals(int* nums, int numsSize) {
5 // Finding the longest increasing sequence
6 int dp_inc[numsSize];
7 memset(dp_inc, 0, sizeof(dp_inc));
8 for (int i = 0; i < numsSize; ++i) {
9 dp_inc[i] = 1;
10 for (int j = 0; j < i; ++j) {
11 if (nums[i] > nums[j]) {
12 dp_inc[i] = (dp_inc[i] > (dp_inc[j] + 1)) ? dp_inc[i] : (dp_inc[j] + 1);
13 }
14 }
15 }
16
17 // Finding the longest decreasing sequence
18 int dp_dec[numsSize];
19 memset(dp_dec, 0, sizeof(dp_dec));
20 for (int i = numsSize - 1; i >= 0; --i) {
21 dp_dec[i] = 1;
22 for (int j = numsSize - 1; j > i; --j) {
23 if (nums[i] > nums[j]) {
24 dp_dec[i] = (dp_dec[i] > (dp_dec[j] + 1)) ? dp_dec[i] : (dp_dec[j] + 1);
25 }
26 }
27 }
28
29 // Calculate the max mountain size using the two arrays
30 int max_size = 0;
31 for (int i = 0; i < numsSize; ++i) {
32 if (dp_inc[i] > 1 && dp_dec[i] > 1) { // Ensure peak is valid
33 max_size = (max_size > (dp_inc[i] + dp_dec[i] - 1)) ? max_size : (dp_inc[i] + dp_dec[i] - 1);
34 }
35 }
36
37 return numsSize - max_size;
38}
39This C solution uses two separate passes to identify the longest increasing and decreasing sequences through the list. By leveraging two pointer variables across arrays (capturing differences in sequences), effective merging occurs. Reduction of the sequence only removes minimal elements required.