thảo luận Leetcode mỗi ngày

class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;
        int[] lis = new int[n];
        int[] lds = new int[n];
        Arrays.fill(lis,1);
        Arrays.fill(lds,1);
        for(int i =0 ; i < n;i++){
            for(int j =i+1 ; j <n;j++ ){
                if(nums[i]<nums[j] ){
                    lis[j] = Math.max(lis[j], lis[i]+1);
                }
                if(nums[n-1-i]<nums[n-1-j]){
                    lds[n-1-j] =Math.max(lds[n-1-j],lds[n-1-i]+1);
                }
            }
        }
        int max =0;
        for(int i =0 ; i < n ; i++){
            if(lis[i]==1 || lds[i]==1) continue;
            if(lis[i]+lds[i]>max){
                max = lis[i]+lds[i];
            }
        }
        return n-max+1;
    }
}

class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;
        int res = n;
        int[] up = new int[n];
        int[] down = new int[n];
        List<Integer> ans = new ArrayList();
        ans.add(nums[0]);
//increasing array
        for(int i = 1;i<n;i++){
            if(nums[i] > ans.get(ans.size()-1))
                ans.add(nums[i]);
            else{
                int low = 0;
                int high = ans.size()-1;
                while(low<high){
                    int mid = (high+low)/2;
                    if(ans.get(mid) < nums[i])
                        low = mid+1;
                    else
                        high = mid;
                }
                ans.set(low,nums[i]);
            }
            up[i] = ans.size();
        }
//decreasing array
        ans.clear();
        ans.add(nums[n-1]);
        for(int i = n-2;i>=0;i--){
            if(nums[i] > ans.get(ans.size()-1))
                ans.add(nums[i]);
            else{
                int low = 0;
                int high = ans.size()-1;
                while(low<high){
                    int mid = (high+low)/2;
                    if(ans.get(mid) < nums[i])
                        low = mid+1;
                    else
                        high = mid;
                }
                ans.set(low,nums[i]);
            }
            down[i] = ans.size();
            
        }
//iterate up and down array
        for(int i = 1;i<n;i++){
            if(up[i]!=1 && down[i]!=1)
                res = Math.min(res,n-up[i]-down[i]+1);
        }
        return res;
        
    }
}

impl Solution {
    pub fn minimum_mountain_removals(nums: Vec<i32>) -> i32 {
        fn lis(nums: &Vec<i32>) -> Vec<i32> {
            let n = nums.len();
            let mut memo = vec![1; n];

            for i in 1..n {
                for j in 0..i {
                    if nums[j] < nums[i] {
                        memo[i] = memo[i].max(memo[j] + 1);
                    }
                }
            }

            memo
        }

        fn lds(nums: &Vec<i32>) -> Vec<i32> {
            let n = nums.len();
            let mut memo = vec![1; n];

            for i in (0..(n - 1)).rev() {
                for j in ((i + 1)..n).rev() {
                    if nums[j] < nums[i] {
                        memo[i] = memo[i].max(memo[j] + 1);
                    }
                }
            }

            memo
        }

        let (lis_memo, lds_memo) = (lis(&nums), lds(&nums));

        let (n, mut max_mountain_len) = (nums.len(), 0);
        for i in 1..(n - 1) {
            if lis_memo[i] > 1 && lds_memo[i] > 1 {
                max_mountain_len = max_mountain_len.max(lis_memo[i] + lds_memo[i] - 1);
            }
        }

        n as i32 - max_mountain_len
    }
}

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        lis = [1] * n
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    lis[i] = max(lis[i], lis[j] + 1)
        lds = [1] * n
        res = 100000000000
        for i in range(n - 1, 0, -1):
            for j in range(n - 1, i, -1):
                if nums[j] < nums[i]:
                    lds[i] = max(lds[i], lds[j] + 1)
                
            if lis[i] == 1 or lds[i] == 1:
                continue
            mountainWidth = lis[i] + lds[i] - 1
            removal = n - mountainWidth
            res = min(res, removal)
        
        return res

class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;
        int[] longestIncreaseSet = new int[n];
        int[] longestDecreaseSet = new int[n];

        Arrays.fill(longestIncreaseSet, 1);
        Arrays.fill(longestDecreaseSet, 1);

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i ; j++) {
                if (nums[i] > nums[j]) {
                    longestIncreaseSet[i] = Math.max(
                        longestIncreaseSet[i],
                        longestIncreaseSet[j] + 1
                    );
                }
            }
        }

        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] > nums[j]) {
                    longestDecreaseSet[i] = Math.max(
                        longestDecreaseSet[i],
                        longestDecreaseSet[j] + 1
                    );
                }
            }
        }

        int longestMountain = -1;
        for (int i = 1; i < n - 1; i++) {
            if (longestIncreaseSet[i] > 1 && longestDecreaseSet[i] > 1) {
                longestMountain = Math.max(
                    longestMountain,
                    longestIncreaseSet[i] + longestDecreaseSet[i] - 1
                );
            }
        }

        return n - longestMountain;
    }
}