专栏首页生物信息学、python、R、linuxMaxSubarray最大子序和问题

MaxSubarray最大子序和问题

回顾leetcode原来做过的题,看到了经典的最大子序和问题,收藏了一个好回答。 这个问题是这样的(https://leetcode.com/problems/maximum-subarray/ ): Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. 就是给一组整数,找到一组连续的子序列,让子序列的和最大,并且返回最大和。 比如说: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 子序列[4,-1,2,1]有最大的和6.

原来是这样做的:

class Solution(object):
    def maxSubArray(self, nums):
        flag = False
        for num in nums:
            if num > 0:
                flag = True
        if flag == True:
            s = 0
            m = 0
            for num in nums:
                s += num
                if s > 0 :
                    if s > m:
                        m = s
                else:
                    s = 0
            return m 
        else:
            return max(nums)

运行时间28ms,在时间上可以超过100%的python答案,不过怎么看怎么罗里吧嗦,而且遍历了两遍。发现在讨论区有个很精简的回答:

class Solution:
    def maxSubArray(self, nums):
        for i in range(1, len(nums)):
            if nums[i-1] > 0:
                nums[i] += nums[i-1]
        return max(nums)

想法非常巧妙。

欢迎关注公众号~

生信编程日常

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 动态规划算法练习(5)--medium

    中文链接:https://leetcode-cn.com/problems/predict-the-winner/ 英文链接:https://leetcode...

    生信编程日常
  • python字典一个key映射多个value

    有时候我们想在字典中存储更多的信息,一个key对应多个value,但是又不想做两个字典。那么,我们可以将多个值放到另外的容器中, 比如列表或者集合中。比如,可以...

    生信编程日常
  • 动态规划算法练习 (1)

    动态规划(英语:Dynamic programming,简称DP)是一种在数学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式...

    生信编程日常
  • Js算法与数据结构拾萃(1)

    算法是为了解决某些问题所提供的精确解法,数据结构是为了支撑算法提供的一种存储结构。

    一粒小麦
  • leetcode-55-跳跃游戏

    1、给定一个vector,里面存放着非负的int型整数,每一个整数代表在这个位置上可以跳跃的步数,要求判断最终能不能跳跃到vector的最后一位。

    chenjx85
  • 漫画:经典鹅厂面试题(4sum - nSum)

    第18题:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + ...

    程序员小浩
  • leetcode-665-Non-decreasing Array

    chenjx85
  • 双指针法:一样的道理,能解决四数之和

    题意:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c ...

    代码随想录
  • Python3刷题系列(三)

    中文版:https://leetcode-cn.com/problems/sqrtx/

    用户5473628
  • 画解算法:219. 存在重复元素 II

    https://leetcode-cn.com/problems/contains-duplicate-ii/

    灵魂画师牧码

扫码关注云+社区

领取腾讯云代金券