专栏首页Android知识点总结[-算法篇-] 最大子序列和

[-算法篇-] 最大子序列和

零、前言

最大子序列和问题

这个问题是《数据结构和算法分析》一书中的一个问题,书中给了四种算法 我感觉它是入手算法很不错的一个问题,本文算法源于书中,但文中包含了我的分析和理解

2.题目的分析

也许很多人看到题目就懵圈了,这里解释一下:

拿一个例子来说: -2,11,-4,13,-5,-2
它的子序列是什么意思: 连续的若干个元素, 比如:11,-4和-4,13,-5,-2等
该问题也就是说:这些子序列元素的和最大是多少,以下列出了所有子序列的情况及子序列和

一、第一种算法

1.具体算法

根据上面分析的图,很容易可以想到第一种算法:

private static int maxSonNum(int[] a) {
    int maxSum = 0;
    for (int i = 0; i < a.length; i++) {
        for (int j = i; j < a.length; j++) {
            int sum = 0;
            for (int k = i; k <= j; k++) {
                sum += a[k];
            }
            if (sum > maxSum) {
                maxSum = sum;
            }
        }
    }
    return maxSum;
}

2.算法分析

可以说下面是我发明的for循环的简单图示:简称for图

[1].一条线代表一个for循环
[2].线的左边是for循环中索引的变量名
[3].线两端数字表示循环的范围,空心代表不包含,实心表示包含
[4].箭头表示某个时刻的遍历情况
[5].内部循环在下边,可以看成底部箭头向右走,走到头上面的箭头右动一格(类似时钟,分针,秒针)

想像一下,看脑中是否可以出现for循环中运动的场景:

k 箭头向右走,计算`i~j`子序列的和,并维护maxSum的值。当走到 j 时,发出"刺啦"一声
j 箭头向右移一格,发出一声"嗒"。然后k箭头再跑,直到j跑到a.length之后  
i 箭头右移一格, 发出一声"叮",j 箭头在k箭头的推动下一点点跑,直到i跑到了a.length

交响乐大概就是这样的吧:
...
刺啦,嗒,刺啦,嗒,刺啦,嗒,叮
刺啦,嗒,刺啦,嗒,刺啦,嗒,刺啦,嗒,叮
刺啦,嗒,刺啦,嗒,刺啦,嗒,刺啦,嗒,刺啦,嗒,叮
...

从上面来看,这个算法虽然可以解决问题,使用了三层,每层都是N的复杂度 时间复杂度为O(N^3),可想而知,非常耗时


二、第二种算法

1.具体算法
private static int maxSonNum(int[] a) {
    int maxSum = 0;
    for (int i = 0; i < a.length; i++) {
        int sum = 0;
        for (int j = i; j < a.length; j++) {
            sum += a[j];
            if (sum > maxSum) {
                maxSum = sum;
            }
        }
    }
    return maxSum;
}

2.算法分析
刚才:在j的循环中新开了一个k循环计算i~j的元素和
如 i=0,j=4 时:子序列 -2,11,-4,13,-5 用一个k循环就算他们的和

这里:在j的循环中维护sum变量也能达到一样的效果:
如 i=0,j=4 时:sum= sum + -5 即 -2+11-4+13-5,然后维护maxSum
这样就减少一层for循环:时间复杂度为O(N^2)

三、第三种算法

1.具体算法

分治的思想,也是本文最想讲的内容

private static int maxSumRec(int[] a, int start, int end) {
    if (start == end) {
        return a[start];//一个元素的最大子序列是其本身
    }
    
    int center = (start + end) / 2;
    int maxLeftSum = maxSumRec(a, start, center);//1.左半最大子序列和
    int maxRightSum = maxSumRec(a, center + 1, end);//2.右半最大子序列和

    /*
    3.如果最大子序列和贯穿左右时:
        |--- 1.子序列是连续的
        |--- 2.中点和中点的后面元素在最大子序列中
    */
    //寻找左半中含左半一个元素的最大子序列和
    int maxLeftSBorderSum = 0, leftBorderSum = 0;
    for (int i = center; i >= start; i--) {
        leftBorderSum += a[i];
        if (leftBorderSum > maxLeftSBorderSum) {
            maxLeftSBorderSum = leftBorderSum;
        }
    }
    //判断右半中含右半第一个元素的最大子序列和
    int maxRightSBorderSum = 0, rightBorderSum = 0;
    for (int i = center + 1; i <= end; i++) {
        rightBorderSum += a[i];
        if (rightBorderSum > maxRightSBorderSum) {
            maxRightSBorderSum = rightBorderSum;
        }
    }
    return max3(maxLeftSum, maxRightSum, maxLeftSBorderSum + maxRightSBorderSum);
}

private static int max3(int a, int b, int c) {
    int max;
    if (a > b && a > c) {
        max = a;
    } else if (c > a && c > b) {
        max = c;
    } else {
        max = b;
    }
    return max;
}

2.算法分析

将一个大问题拆解成若干个小问题,使用递归来解决 虽然算法复杂了很多,但运行的时间复杂度降到了O(NlongN),还是很有价值的

最大子序列和可能存在于:
1.左半的序列:maxLeftSum
2.由半的序列:maxRightSum
3.该序列贯穿左右
    |--- 判断左半(子序列含:左半最后一个元素):maxLeftSBorderSum
    |--- 判断右半(子序列含:右半第一个元素):maxRightSBorderSum
寻找子序列即(含左半最后一个元素),又含(右半第一个元素),说明两半序列可连续

int maxLeftSBorderSum = 0, leftBorderSum = 0;
for (int i = center; i >= start; i--) {//遍历包含center点的最侧子序列取最大和
    leftBorderSum += a[i];
    if (leftBorderSum > maxLeftSBorderSum) {
        maxLeftSBorderSum = leftBorderSum;
    }
}

int maxRightSBorderSum = 0, rightBorderSum = 0;
for (int i = center + 1; i <= end; i++) {//遍历包含center+1点的右侧子序列取最大和
    rightBorderSum += a[i];
    if (rightBorderSum > maxRightSBorderSum) {
        maxRightSBorderSum = rightBorderSum;
    }
}
maxLeftSBorderSum和maxRightSBorderSum由于包含center点和center+1点
所以是贯穿左右的子序列,并且其和是[贯穿左右的子序列]中最大的

具体来分析一下问题的分解

Q1: 求 -2 11 -4 13 -5 -2 的最大子序列和

Q1可以分解为下面三个问题的最大值:
    |---Q1.1: -2 11 -4 的最大子序列和
    |---Q1.2: 13 -5 -2 的最大子序列和
    |---Q1.3: 序列和最大值贯穿左右时的最大值:
        |--- 判断左半:序列含左半最后一个元素的子序列最大值
        |--- 判断右半:序列含右半第一个元素子序列最大值
        
Q1.1可以分解为下面三个问题的最大值:
    |---Q1.1.1: -2 11  的最大子序列和
    |---Q1.1.2: -4     的最大子序列和 -4
    |---Q1.1.3: 序列和最大值贯穿左右时的最大值:
        |--- 判断左半:序列含左半最后一个元素的子序列最大值 11
        |--- 判断右半:序列含右半第一个元素子序列最大值 -4

Q1.1.1可以分解为下面三个问题的最大值:
    |---Q1.1.1.1: -2     的最大子序列和 -2
    |---Q1.1.1.2: 11     的最大子序列和 11
    |---Q1.1.1.3: 序列和最大值贯穿左右时的最大值:
        |--- 判断左半:序列含左半最后一个元素的子序列最大值 -2
        |--- 判断右半:序列含右半第一个元素子序列最大值 11

所以 Q1.1.1 = 11        Q1.1.2 = -4         Q1.1.3 = 7
所以 Q1.1 = 11          同理分解 Q1.2 = 13  Q1.3 = 7 + 13 =20 
所以 Q1 = 20 得解

四、 第四种算法

1.具体算法
private static int maxSonNum4(int[] a) {
    int maxSum = 0, sum = 0;
    for (int i = 0; i < a.length; i++) {
        sum += a[i];
        if (sum > maxSum) {
            maxSum = sum;
        } else if (sum < 0) {
            sum = 0;
        }
    }
    return maxSum;
}

2.分析

反正我是很难想像第一个写出这个算法的人脑子是怎么想的,也很难去说明这个算法的正确性 这在O(N)的时间完成了最大子序列和问题,这种"简洁和聪明以及高效"也许就是算法的迷人之处。

 -2 11 -4 13 -5 -2 
                sum         maxSum      sum
 i = 0          -2            0          0
 i = 1          11            11         11
 i = 2          7             11         7
 i = 3          20            20         20
 i = 4          15            20         15
 i = 5          13            20         13

一种算法可以从O(N^3)优化到O(N^2),再用分治优化到O(NlogN) 最后被一个O(N)的算法亮瞎的的钛合金言,所以这个问题真的挺有意思。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Android粒子篇之Bitmap像素级操作

    张风捷特烈
  • 06--图解数据结构之并查集

    张风捷特烈
  • Android原生绘图进度条+简单自定义属性代码生成器

    张风捷特烈
  • Netty与传统Server对比

    前言 本文旨在介绍传统Socket服务端与NIO服务端的差异. 以餐厅服务员简单举例,每个客人对应一个请求. 传统Socket / OIO 1 public ...

    用户1216491
  • 一个简单易用的图标字体库和CSS框架fontawesome

    font-awesome.css里对.fa-camera-retro:before的定义:\f083

    Jerry Wang
  • mysql导入导出数据

    在mysql workbench里面对需要导入的表右键—>table data import wizard,选择刚才保存的utf-8编码的csv文件,选择nex...

    hankleo
  • 剑指offer 栈的压入,弹出序列

    输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序...

    week
  • 16(套接字)

    套接字描述符在Unix系统中是用文件描述符实现的。事实上,许多处理文件描述符函数(read和write)都可以处理文件描述符 要创建一个套接字,可以调用so...

    提莫队长
  • Android原生绘图进度条+简单自定义属性代码生成器

    张风捷特烈
  • MySQL Ripple 一款开源的MySQL binlog server软件

    MySQL Ripple 是有google开源的一款工具,地址 https://github.com/google/mysql-ripple

    用户1278550

扫码关注云+社区

领取腾讯云代金券