LIS
unknown
java
a year ago
4.7 kB
70
Indexable
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){ } }
Editor is loading...
Leave a Comment