襄阳做网站的,昆明网红打卡景点,做木业网站怎样起名,品牌网站制作公司目录
一、最大子段和
1、什么是最大子段和
2、暴力枚举
3、分治法
4、动态规划
二、最长公共子序列
1、什么是最长公共子序列
2、暴力枚举法
3、动态规划法
4、完整代码 一、最大子段和
1、什么是最大子段和 子段和就是数组中任意连续的一段序列的和#xff0c;而…目录
一、最大子段和
1、什么是最大子段和
2、暴力枚举
3、分治法
4、动态规划
二、最长公共子序列
1、什么是最长公共子序列
2、暴力枚举法
3、动态规划法
4、完整代码 一、最大子段和
1、什么是最大子段和 子段和就是数组中任意连续的一段序列的和而最大子段和就是寻找子段和里最大的一个值。下面的解释中S[l,r]会用来表示l到r的子段和l和r分别表示左值和右值。 最大子段和一般有三种解决方案暴力枚举法分治法动态规划法。下面将逐个介绍。 2、暴力枚举 暴力枚举就是遍历所有的子段和寻找最大的子段和时间复杂度 。相对无脑直接贴上代码。 //暴力枚举法public static int maxsize_violate(ArrayListIntegerarr,int left, int right){int max-99999999;for(int ileft;iright;i){int sum0;for(int ji;jright;j){for(int ki;kj;k){sumarr.get(k); //最大值来源}if(summax)maxsum;sum0;}}return max;}
3、分治法 将每个问题分解为三个小问题左一半的子段和右一半的子段和必须跨区域的子段和。 伪代码如下可以看到左子段和与右子段和都是递归求解3、4跨区域的一定是左右两个子段和最大值的和5、6、7最后选择左子段和、右子段和、跨域子段和中最大的子段和8、9。 完整代码 //分治法public static int maxsize(ArrayListIntegerarr, int left, int right){int sum0,midSum0,leftSum0,rightSum0;int center,s1,s2,lefts,rights;//左右相等返回左值if (leftright){ sumarr.get(left);}//否则分治法else {center(leftright)/2;leftSummaxsize(arr,left,center); //leftlr/2 //左区间最大值rightSummaxsize(arr,center1,right); //lr/21right //右区间最大值//后面都是在计算跨区域最大值必须跨区域一定是左区间贴近边界的最大值加右区间贴近边界的最大值相加。s10;lefts0; //s1存左侧区间最大值lefts作为tempfor (int icenter;ileft;i--){leftsarr.get(i);if (leftss1){s1lefts;}}s20;rights0; //s2存右侧区间最大值rights作为temp for (int jcenter1;jright;j){rightsarr.get(j);if (rightss2){s2rights;}}midSums1s2; //中间跨域的等于左侧加右侧的if (midSumleftSum){sumleftSum;}else {summidSum;}if (sumrightSum){sumrightSum;}}return sum;}
4、动态规划 动态规划法是自底向上推导假设为第i个数为包含最后一个数的连续子段和sum为最大子段和。 建立于下面图这个关系假设已经有到的子段和,那么加入后一个生成只有两种可能
1,那么
2,那么 对于的每一个都要与sum取最大值保证sum为到中最大的值返回sum。 完整代码 //动态规划法public static int maxsum(ArrayListIntegerarr, int n){int sum-999999;int b0;for(int i0;in;i){if(b0)barr.get(i);else barr.get(i);if(bsum)sumb;}return sum;}
二、最长公共子序列
1、什么是最长公共子序列 子序列是指序列中任意不一定连续但顺序的若干个字符组成的序列。如下图中Z1{B,C,A}为X的子序列B,C,A三个字符在X中顺序出现且不一定连续。 公共子序列就是指两个序列之间存在一个共同的子序列而我们就是要找到最长的一个公共子序列。 2、暴力枚举法 暴力枚举法不仅占用了相当大的内存存放所有子序列和所有公共子序列而且浪费了巨大的时间时间复杂度指数级。 3、动态规划法 动态规划法仍然是这种自底向上的算法讨论前一项的最长公共子序列通过比较两个序列下一个值判定是否进入子序列。动态规划法的时间复杂度为Omn。 使用c[i][j]数组记录和的最长公共子序列长度 b[i][j]数组记录子序列的产生情况。c数组存在下面的递归结构成立与b数组的关系如下根据这个递推式可以写出c和b数组的生成函数。 c[i][j]c[i-1][j-1]1 b[i][j]1 ↖ c[i][j]c[i-1][j] b[i][j]2↑ c[i][j]c[i][j-1] b[i][j]3← 如何构造最长子序列 就是根据b数组的指引倒推子序列所有b[i][j]1也就是b数组指引为左上箭头的都是公共序列的值将他们按顺序串接就得到了最大子序列。 注意一个问题X序列是y轴方向的Y序列是x轴方向的。
4、完整代码
//最长公共子序列
import java.util.Scanner;
public class LCS {public static void main(String [] args){String xnew Scanner(System.in).nextLine();String ynew Scanner(System.in).nextLine();int mx.length();int ny.length();int [][]cnew int[m1][n1];int [][]bnew int[m1][n1];LCSLength(x, y, c, b);for(int i0;im1;i){for(int j0;jn1;j){System.out.print(c[i][j]);System.out.print(\t);}System.out.println();}BuildLCS(m,n,x,b);}//最长公共子序列生成c和b数组public static void LCSLength(String x,String y,int [][]c,int [][]b){int i,j;int mx.length();int ny.length();for(i0;im1;i)c[i][0]0;for(i0;in1;i)c[0][i]0;for(i1;im1;i){for(j1;jn1;j){if(x.charAt(i-1)y.charAt(j-1)){c[i][j]c[i-1][j-1]1;b[i][j]1;}else if(c[i-1][j]c[i][j-1]){c[i][j]c[i-1][j];b[i][j]2;}else{c[i][j]c[i][j-1];b[i][j]3;}}}}//构造最长公共子序列public static void BuildLCS(int i,int j,String x,int[][]b){if(i0|j0){return;}if(b[i][j]1){BuildLCS(i-1, j-1, x, b);System.out.print(x.charAt(i-1));}else if(b[i][j]2){BuildLCS(i-1,j,x,b);}else{ BuildLCS(i, j-1, x, b);}}
}
