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.
1public class Solution {
2 public int minMountainRemovals(int[] nums) {
3 int n = nums.length;
4 int[] lis = new int[n];
5 int[] lds = new int[n];
6 Arrays.fill(lis, 1);
7 Arrays.fill(lds, 1);
8
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] = Math.max(lis[i], lis[j] + 1);
13 }
14 }
15 }
16
17 for (int i = n - 1; i >= 0; i--) {
18 for (int j = n - 1; j > i; j--) {
19 if (nums[i] > nums[j]) {
20 lds[i] = Math.max(lds[i], lds[j] + 1);
21 }
22 }
23 }
24
25 int maxMountain = 0;
26 for (int i = 0; i < n; i++) {
27 if (lis[i] > 1 && lds[i] > 1) {
28 maxMountain = Math.max(maxMountain, lis[i] + lds[i] - 1);
29 }
30 }
31
32 return n - maxMountain;
33 }
34}
35In this Java solution, we use arrays to compute LIS and LDS at each index, followed by calculating the maximum possible mountain length. The difference between total elements and this length yields the minimum removals needed.
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 <vector>
2#include <algorithm>
3using namespace std;
4
5int minMountainRemovals(vector<int>& nums) {
6 int n = nums.size();
7 vector<int> lis(n, 1), lds(n, 1);
8
9 for (int i = 0; i < n; ++i)
10 for (int j = 0; j < i; ++j)
11 if (nums[i] > nums[j]) lis[i] = max(lis[i], lis[j] + 1);
12
13 for (int i = n - 1; i >= 0; --i)
14 for (int j = n - 1; j > i; --j)
15 if (nums[i] > nums[j]) lds[i] = max(lds[i], lds[j] + 1);
16
17 int maxMountain = 0;
18 for (int i = 0; i < n; ++i)
19 if (lis[i] > 1 && lds[i] > 1)
20 maxMountain = max(maxMountain, lis[i] + lds[i] - 1);
21
22 return n - maxMountain;
23}
24In this C++ approach, we employ vectors to handle dynamic programming values pertinent to the longest increasing and decreasing sequences. Through pointer-based calculations, minimal elements are left, guiding efficient penalty-based mountain creation.