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

柔光的暖阳◎ 2023-07-06 05:00 36阅读 0赞

### 文章目录 ###

*  1.最大子列和问题
 *   *  算法1:
     *  算法2：
     *  算法3：
     *  算法4,在线处理:
 *  总结:

# 1.最大子列和问题 #

![在这里插入图片描述][20200216153719545.png]  
![在这里插入图片描述][20200216171519382.png]

## 算法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);
        }
    }

运行结果:  
![在这里插入图片描述][20200216170915558.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1_size_16_color_FFFFFF_t_70 1]

## 算法2： ##

![在这里插入图片描述][20200216171921164.png]

//算法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);
        }

![在这里插入图片描述][20200216184541397.png]  
![在这里插入图片描述][20200216184557720.png]

## 算法3： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1_size_16_color_FFFFFF_t_70 2]  
但是这个仍不是最快的算法.

## 算法4,在线处理: ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][20200216195813532.png]

//算法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;
        }

![在这里插入图片描述][20200216201959660.png]

# 总结: #

![在这里插入图片描述][20200216202025225.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1_size_16_color_FFFFFF_t_70 4]

--------------------

完

[20200216153719545.png]: https://img-blog.csdnimg.cn/20200216153719545.png
[20200216171519382.png]: https://img-blog.csdnimg.cn/20200216171519382.png
[20200216170915558.png]: https://img-blog.csdnimg.cn/20200216170915558.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200216184303496.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200216171749727.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1,size_16,color_FFFFFF,t_70
[20200216171921164.png]: https://img-blog.csdnimg.cn/20200216171921164.png
[20200216184541397.png]: https://img-blog.csdnimg.cn/20200216184541397.png
[20200216184557720.png]: https://img-blog.csdnimg.cn/20200216184557720.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200216190657452.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200216195759356.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1,size_16,color_FFFFFF,t_70
[20200216195813532.png]: https://img-blog.csdnimg.cn/20200216195813532.png
[20200216201959660.png]: https://img-blog.csdnimg.cn/20200216201959660.png
[20200216202025225.png]: https://img-blog.csdnimg.cn/20200216202025225.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200216202051188.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzIxMzQ5NjM1,size_16,color_FFFFFF,t_70