LIS

class DP {
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;

        int[] LISdp = new int[n];

        for(int i=0; i<n; i++){
            int ele = nums[i];

            LISdp[i] = 1;

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

        int[] LDSdp = new int[n];
        for(int i=n-1; i>=0; i--){
            int ele = nums[i];

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

        int maxMountainArrayLength = 0;
        
        for(int i=0; i<n; i++){
            if(LISdp[i] == 1 || LDSdp[i] == 1){ // you are not strictly increasing or decreasing
                continue;
            }

            maxMountainArrayLength = Math.max(maxMountainArrayLength, LISdp[i] + LDSdp[i]  - 1);
        }

        return (n - maxMountainArrayLength);
    }
    // leetcode 300
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;

        int[] dp = new int[n];
        int lis = 0;

        for(int i=0; i<n; i++){
            int ele = nums[i];

            dp[i] = 1;

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

            lis = Math.max(lis, dp[i]);
        }

        return lis;
    }

    public static int lps_rec(String str, int i, int j){
        if(i>j){
            return 0;
        }

        if(i==j){
            return 1;
        }

        int ans = 0;
        if(str.charAt(i) == str.charAt(j)){
            ans = lps_rec(str, i+1, j-1) + 2;
        } else {
            ans = Math.max(lps_rec(str, i+1, j), lps_rec(str, i, j-1));
        }

        return ans;
    }

    public static int lps_memo(String str, int i, int j, int[][] dp){
        if(i>j){
            return dp[i][j] = 0;
        }

        if(i==j){
            return dp[i][j] = 1;
        }

        if(dp[i][j] != 0){
            return dp[i][j];
        }

        int ans = 0;
        if(str.charAt(i) == str.charAt(j)){
            ans = lps_memo(str, i+1, j-1, dp) + 2;
        } else {
            ans = Math.max(lps_memo(str, i+1, j, dp), lps_memo(str, i, j-1, dp));
        }

        return dp[i][j] = ans;
    }

    public static int lps_tab(String str, int i, int j, int[][] dp){
        int n = str.length();
        for(int diag = 0; diag<n; diag++){
            for(i=0, j=diag; j<n; i++, j++){
                if(i==j){
                    dp[i][j] = 1;
                    continue;
                }

                int ans = 0;
                if(str.charAt(i) == str.charAt(j)){
                    ans = dp[i+1][j-1] + 2; //lps_memo(str, i+1, j-1, dp) + 2;
                } else {
                    ans = Math.max(dp[i+1][j], dp[i][j-1]);//Math.max(lps_memo(str, i+1, j, dp), lps_memo(str, i, j-1, dp));
                }

                dp[i][j] = ans;
            }
        }

        return dp[0][n-1];
    }



    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        return lps_tab(s,0,n-1, dp);
    }


    public boolean rec(int[] nums, int n, int tar){
        if(tar == 0){
            return true;
        }

        if(n==0){
            return false;
        }

        boolean ans = rec(nums, n-1, tar); // no call

        if(tar - nums[n-1] >= 0){
            ans = ans || rec(nums, n-1, tar-nums[n-1]); // yes call
        }

        return ans;
    }


    public boolean rec_memo(int[] nums, int n, int tar, Boolean[][] dp){
        if(tar == 0){
            return dp[n][tar] = true;
        }

        if(n==0){
            return dp[n][tar] = false;
        }

        if(dp[n][tar] != null){
            return dp[n][tar];
        }

        boolean ans = rec_memo(nums, n-1, tar, dp); // no call

        if(tar - nums[n-1] >= 0){
            ans = ans || rec_memo(nums, n-1, tar-nums[n-1], dp); // yes call
        }

        return dp[n][tar] = ans;
    }
    public boolean canPartition(int[] nums) {
        int n = nums.length;

        int sum = 0;
        for(int i=0; i<n; i++){
            sum += nums[i];
        }    

        if(sum % 2 != 0){
            return false;
        }

        int tar = sum/2;

        Boolean[][] dp = new Boolean[n+1][tar+1]; // -1 -> no answer, 0 -> false, 1 -> true
        
        return rec_memo(nums, n, tar, dp);
    }
    public static void main(String[] args){
        
    }
}