数据结构(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;
}

总结:

---

完