最长递增子序列,最大连续子序列和,最大连续子序列乘积,最长公共子序列,最长公共子串
//最长递增子序列
//DP,dp[i]表示以nums[i]结尾的子序列中递增子序列的最大长度,所以dp[i]=max{dp[j]+1} if nums[j]<=nums[i],0=<j<i
public int LIS(int[] nums){
int [] dp = new int [nums.length]{1};
for(int i = 1;i < nums.length;i++){
for(int j = 0; j < i; j++){
if(nums[j] <= nums[i]) dp[i] = max(dp[j]+1,dp[i]);
}
}
int res = 0;
for(int i = 0 ; i < dp.length; i++){
res = max(res,dp[i]);
}
return res;
}
//最大连续子序列和
//DP,dp[i]表示以i为止数值结尾的最大连续子序列和,如果dp[i]<0则dp[i]=nums[i],否则dp[i]=dp[i-1]+nums[i],也就是说dp[i]=max{nums[i],dp[i-1]+nums[i]}
public int maxConsecutiveSubsetSum(int[] nums){
int[] dp= new int[nums.length];
dp[0]=nums[0];
for(int i =1 ; i < nums.length; i++){
dp[i]=Math.max(nums[i],dp[i-1]+nums[i]);
}
int res = Integer.MIN_VALUE;
for(int i = 0 ; i < nums.length; i++){
res = Math.max(dp[i],res);
}
return res;
}
//最大连续子序列和问题,可以用上面的DP,也可以用分治算法,时间复杂度O(nlogn)。
public int maxSubseqSum(int [] nums){
if(nums==null || nums.length==0) return 0;
return maxSubseqSumHelper(nums,0,nums.length-1);
}
public int maxSubseqSumHelper(int[] nums,int left,int right){
if(left==right) return nums[left];
int left_mss = maxSubseqSumHelper(nums,left,(left+right)/2);
int right_mss = maxSubseqSumHelper(nums,(left+right)/2+1,right);
int mid_to_left = Integer.MIN_VALUE,mid_to_right=Integer.MIN_VALUE;
int sum = 0 ;
for(int i = mid; i >= left; i--){
sum = sum+nums[i];
mid_to_left = Math.max(mid_to_left,sum);
}
sum = 0;
for(int i = mid+1;i <= right; i++){
sum = sum+nums[i];
mid_to_right = Math.max(mid_to_right,sum);
}
int result = Math.max(left_mss,right_mss);
return Math.max(res,mid_to_left+mid_to_right);
}
//最大连续子序列乘积
//DP,但是由于需要是连续的,而且乘积尽量大的话可以前面最小的负值积和一个负值相乘得到,或者前面最大的正值和一个正值相乘得到。
public int maxProductConsecutiveSubset(int[] nums){
int [] min_val = new int[nums.length];
int [] max_val = new int[nums.length];
maxdp[0]=mindp[0]=nums[0];
for(int i = 1; i < nums.length;i++){
maxdp[i] = Math.max(nums[i],maxdp[i-1]*nums[i],mindp[i-1]*nums[i]);
mindp[i] = Math.min(nums[i],maxdp[i-1]*nums[i],mindp[i-1]*nums[i]);
}
int res = Integer.MIN_VALUE;
for(int i = 0 ; i < maxdp.length; i++){
if(maxdp[i] > res) res=maxdp[i];
}
return res;
}
//最长公共子序列问题
//二维DP来求解,设定dp[i][j]代表第一个字符串到第i个字符为止和第二个字符串到第j个字符为止最大的公共子序列
//如果s[i]=t[j]则dp[i][j]=dp[i-1][j-1]+1,否则dp[i][j]=max{dp[i][j-1],dp[i-1][j]},其中dp[i][0]=dp[0][j]=0
public static int lcs(String str1,String str2){
int len1 = str1.length();
int len2 = str2.length();
int[][] c = new int[len1+1][len2+1];
for(int i = 0 ;i <= len1;i++){
for(int j = 0 ; j <= len2;j++){
if(i==0 || j==0)
c[i][j]=0; //初始值设定
else if(str1.charAt(i-1)==str2.charAt(j-1))//这里的i指的是字符串第i个字符,i-1指的是i-1索引处的字符
c[i][j] = c[i-1][j-1]+1;
else
c[i][j] = Math.max(c[i-1][j],c[i][j-1]);
}
}
return c[len1][len2];
}