数据结构(8) -- 算法应用实例

数据结构(8) -- 算法应用实例

文章目录

​​1.最大子列和问题​​

​​算法1:​​​​算法2：​​​​算法3：​​​​算法4,在线处理:​​

​​总结:​​

1.最大子列和问题

算法1:

public class Demo5 { static int[] list = {-2, 11, -4, 13, -5, -2}; //算法1： public static int maxSubseqSum1(int[] list) { int length = list.length; int i, j, k; int thisSum, maxSum = 0; for (i = 0; i < length; i++) { //i是子列子列左端位置 for (j = i; j < length; j++) { //j是子列右端位置 thisSum = 0; //thisSum是list[i]到list[j]的子列和 for (k = i; k <= j; k++) { thisSum += list[k]; if (thisSum > maxSum) { maxSum = thisSum; } } } } return maxSum; } public static void main(String[] args) { int i = maxSubseqSum1(list); System.out.println(i); }}

运行结果:

算法2：

//算法2： public static int maxSubseqSum2(int[] list) { int length = list.length; int i, j, k; int thisSum, maxSum = 0; for (i = 0; i < length; i++) { //i是子列子列左端位置 thisSum = 0; //thisSum是list[i]到list[j]的子列和 for (j = i; j < length; j++) { //j是子列右端位置 thisSum += list[j ]; if (thisSum > maxSum) { //如果刚得到的这个子列和更大 maxSum = thisSum; //则更新结果 } } } return maxSum; } public static void main(String[] args) { int sum1 = maxSubseqSum1(list); int sum2 = maxSubseqSum1(list); System.out.println("算法1;" + sum1); System.out.println("算法2;" + sum2); }

算法3：

但是这个仍不是最快的算法.

算法4,在线处理:

//算法4：在线处理/算法4：在线处理 public static int maxSubseqSum4(int[] list) { int thisSum, maxSum; thisSum = maxSum = 0; for (int i = 0; i < list.length; i++) { thisSum += list[i]; //向右累加 if (thisSum > maxSum) { maxSum = thisSum; //发现更大和则更新当前结果 }else if (thisSum < 0) {//如果当前子列和为负 thisSum = 0; //则不可能使后面的部门和增大，抛弃之。 } } return maxSum; }

总结:

完

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。