从零打卡leetcode之day 3--最大子序列

前言

深知自己在算法方面上很菜,于是打算通过打卡的方式,逼自己一把。每天在leetcode上打卡,并且把自己的想法分享出来。这将是一段漫长而又艰辛的旅程。如果你也想和我一起走上一条充满艰辛的航路,那么,别犹豫了,上车吧,一起学习一起探讨。

吐槽下:发的有点晚了,本来早早就发的。不知为啥,复制到公众号里的代码好好的,用markdown渲染一下也是好好的,但是点击一保存或者一预览内容,代码的格式就会各种 错乱,搞了我好久,最后还不小心把我弄好的markdown渲染的css样式给删除了......最后还粘贴不了图片....奔溃啊。加上写了两篇文章...

从零打卡leetcode之day 3

题目描述:
给定一个int类型的数组,求最大子序列的和。
也就是说,从这个数组中截取一个子数组,
这个子数组的元素和最大。

例如:
-1 20 -4 14 -4 -2 
这个数组的最大字序列和为30。即20 -4 14。

解题

1.初级版解法

对于这道题,其实我们可以采取遍历所有可能的组合,然后再比较哪种组合的和最大。

也就是说,我们可以找出所有子序列,然后逐个比较。代码如下。

    public int solve(int[] arrs){    
        int max = 0;//用来存放目标子序列的和
        int temp = 0;//用来存每个子序列的和
        for(int i = 0; i < arrs.length; i++){     
                for(int j = i; j < arrs.length; j++){
                temp = 0;         
                //计算子序列的和
                for(int k = 0; k < arrs.length; k++){
                    temp += arrs[k];
                }                
                //进行比较
                if(temp > max){
                    max = temp;
                }
            }
        }       
        return max;
    }`

在这三个循环中,外面两个循环枚举出所有子序列,第三个循环计算子序列的和。

看到三个for循环,时间复杂度的O(n3)。这速度,实在是太慢了。我们来优化优化。

2.进阶版

其实,你仔细看一下里面的那两层for循环,会发现其实可以把它们合并成一个for循环的。

也就是说,我们可以在枚举所有子序列的过程中,是可以一边进行数据处理的。还是直接看代码好理解点。如下:

    public int solve2(int[] arrs){    
        int max = 0; 
        int temp = 0;    
        for(int i = 0; i < arrs.length; i++){
            temp = 0;      
            for(int j = i; j < arrs.length; j++){                
                //一边处理数据
                temp += arrs[j];                
                //进行比较选择                
                if(max < temp){
                    max = temp;
                }
            }
        }      
       return temp;
    }

该方法用了两个for循环,时间复杂度为O(n2),相对来说好了一点。

3.再次优化进阶

这次,我们可以使用递归的思想来处理。递归最重要的就是要找到:

  1. 递归的结束条件
  2. 把问题分解成若干个子问题。

对于这道题,其实我们可以把序列分成左右两部分。那么,最大子序列和的位置会出现在以下三种情况:

  1. 子序列完全在左半部分。
  2. 子序列完全在右半部分。
  3. 一部分在左,一部分在右。

所以我们只要分别求出左半部分的最大子序列和、右半部分的最大子序列和(注意,问题已经转化为求左右两部分的最大子序列和了,也就是说问题被分解成若干子问题了)、以及跨越左右两部分的最大子序列和。最后比较三者之中哪个比较大就可以了。

如何求解左半部分和右半部分的最大子序列?

其实道理一样,把左半部分和右半部分再次分解左右两部分就可以了。

那么,如何求解跨越左右两部分的最大子序列呢?

其实只要求出包含左半部分中最右边元素的子序列的最大和,以及求出包含右半部分中最左边元素的子序列的最大和,然后让两者相加,即可求出跨域左右两部分的最大子序列和了。

子问题已经分解出来了,那么递归的结束条件是什么?

我们把数组分成左右两部分,其实当左右两部分只有一个元素时,递归结束。

这道题的递归思路算是找出来了,不过,代码实现?假如你对递归不大熟悉的话,可能在实现上还是有那么点困难的。对于递归的学习,大家也可以看我写的关于递归与动态规划的几篇文章。

我就直接抛代码了。

    //递归版本
    public int solve3(int[] arrs, int left, int right){    
        int max = 0; 
        //表示只有一个元素,无需在分解
        if(left == right){            
        //为什么?因为低于0的数肯定不可以是最大值的       
        //大不了最大值为0
            max = arrs[left] >= 0 ? arrs[left]:0;
        }else{            
            int center = (left + right)/2;            
            //求解左半部分最大子序列
            int leftMax = solve3(arrs, left, center);            
            //求解右半部分最大子序列
            int rightMax = solve3(arrs, center+1, right);  
                      
            //求解kua跨越左右两部分的最大子序列
            //1.求包含左部分最右元素的最大和
            int l = 0;            
            int l_max = 0;            
            for(int i = center; i >= left; i--){
                l += arrs[i];                
                if(l > l_max){
                    l_max = l;
                }
            }            
             //2.求包含右部分最左元素的最大和
            int r = 0;           
            int r_max = 0;           
            for(int i = center+1; i <= right; i++){
                r += arrs[i];                
                if(r > r_max){
                    r_max = r;
                }
            }            
               //跨越左右两部分的最大子序列
             max = l_max + r_max;            
               //取三者最大值
            if(max < leftMax) max = leftMax;            
            if(max < rightMax) max = rightMax;
        }        
       return max;
    }

递归求解方法的时间复杂度为O(nlgn)。这速度,比第一种做法,不知道快了几个级别….

递归解法可以说是很快的了

但是,等等,我还是不满意…

4.最终版:动态规划

接下来的最终版,时间复杂度可以缩减到O(n), 虽然说是采用了动态规划的思想,不过,我觉得你没学过动态规划也可以看懂。

假如我给你

1 2 -4 5 6

五个元素,你在计算前面三个元素的时候,即

1 + 2 + -4 = -1

发现前面三个元素的和是小于0的,那么,这个

1 2 -4

的子序列我们还要吗?显然,这个子序列的和都小于0了,我们是可以直接淘汰的。因为如果还要这个子序列的话,它和后面的5一相加,结果变成了4,我们还不如让我们的目标子序列直接从5开始呢。

先看代码吧,可能反而会好理解点

    //基于动态规划的思想
    public int solve4(int[] arrs){    
        int max = 0;//存放目标子序列的最大值
        int temp = 0;//存放子序列的最大值

        for(int i = 0; i < arrs.length; i++){
            temp += arrs[i];            
            if(temp > max){
                max = temp;
            }else{                
            //如果这个子序列的值小于0,那么淘汰
            //从后面的子序列开始算起
                if(temp < 0){
                    temp = 0;
                }
             }
        }        
       return max;
    }

这道题不是leetcode上的题目,不过我觉得这道题很不错,所以拿出来分享给大家。

如果你有什么不大清楚的,欢迎微信群里讨论,当然也可以直接来问我勒。欢迎转发让更多人加入打卡行列勒。

如果这道题能对你有所帮助,不妨点个赞。哈哈

原文发布于微信公众号 - 苦逼的码农(di201805)

原文发表时间:2018-08-06

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

2017.10.23解题报告

预计分数:100+60+0=160 实际分数:100+80+0=180 T1 题目描述 现在有一个字符串,每个字母出现的次数均为偶数。接下来我们把第一次出现的字...

36950
来自专栏用户2442861的专栏

百度 阿里 华为 腾讯 谷歌面试笔试题及解析

点评:其余题目请参见:http://blog.csdn.net/doc_sgl/article/details/11695671。 2、一个有10亿条记录...

85230
来自专栏程序员叨叨叨

6.2 逻辑操作符(Logical Operators)

Cg语言中有3种逻辑操作符(也被称为boolean Operators),如表 2 所示,逻辑操作符运算后的返回类型均为bool类型。

9630
来自专栏Crossin的编程教室

【每周一坑】乒乓数

刚从假期回来,又要迎接周末,各位看官想必都很辛苦,所以本周每周一坑为大家准备一道简单的甜点题目,本题取材于伯克利大学 CS61 课程 homework02。 求...

32360
来自专栏数据结构与算法

2488 绿豆蛙的归宿

2488 绿豆蛙的归宿 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 黄金 Gold 题目描述 Description   随着...

1.2K70
来自专栏谦谦君子修罗刀

程序员面试闪充--UML类图关系

我们曾借白茶清欢等一个人,曾借花开花落叹宠辱不惊。今天借着类图来了解面向对象又有何不可呢? 小视频传送门:小视频传送门 ? 对象模型中,类图是来描述系统的静态结...

425120
来自专栏数据结构与算法

P3376 【模板】网络最大流

题目描述 如题,给出一个网络图,以及其源点和汇点,求出其网络最大流。 输入输出格式 输入格式: 第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个...

31380
来自专栏小樱的经验随笔

HDU 1728 逃离迷宫(DFS经典题,比赛手残写废题)

逃离迷宫 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

36470
来自专栏大数据挖掘DT机器学习

【手把手教你做项目】自然语言处理:单词抽取/统计

作者 白宁超 成都信息工程大学硕士。 近期关注数据分析统计学、机器学习。 原文:http://www.cnblogs.com/baiboy/p/zryy1.h...

360130
来自专栏JadePeng的技术博客

从编辑距离、BK树到文本纠错

搜索引擎里有一个很重要的话题,就是文本纠错,主要有两种做法,一是从词典纠错,一是分析用户搜索日志,今天我们探讨使用基于词典的方式纠错,核心思想就是基于编辑距离,...

69260

扫码关注云+社区

领取腾讯云代金券