专栏首页程序员的碎碎念LeetCode每日一题53: 最大子序和

LeetCode每日一题53: 最大子序和

前两天由于开题报告暂停了一下,今天我们继续来刷题.

今天是一道简单难度的题, 认真考虑好可能的情况, 把思路写下来会更容易完成噢.


题目

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

进阶:如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。


思路

从给出的示例中引出了第一种容易想到的情况, 也就是和大于0的情况 我们可以设置一个最大值变量 result(为了避开 Python 中的内置函数 max), 每次都加上 nums[i] 与当前最大值比较大小. 大则替换, 否则不变.

class Solution:
    def maxSubArray(self, nums):
        sum = 0
        max = nums[0]
        for i in nums:
            if sum + i > 0 and sum >= max:
                sum += i
                max = sum
        return max

但是如果示例是和小于0呢? 比如样例是 [-2, -1] 的情况下, 上述的代码就覆盖不了了. 因此还需判断和小于0的情况, 小于0时直接替换, 并于当前最大值比较即可.

总的思路如下:遍历: 当前 sum >0, 直接加上nums[i], 与当前最大值比较大小. 否则, 与当前nums[i], 最大值比较.


实现

只遍历一次, 时间复杂度为 O(n), 只要判断不多, 结果都能超过 90% 以上的用户, 如果你发现没有这么快, 也可能是 LeetCode 抽风了, 再提交几次.

Python 实现

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sum = 0
        max = nums[0]
        for i in nums:
            if sum + i > 0 and sum >= max:
                sum += i
                max = sum
        return max

C实现

C语言实现上, 我使用了 #defineMAX 来比较两数的最大值, 代替了直接使用三目运算符的做法, 从8ms 减至 4ms.

#define MAX(a, b) ((a) > (b) ? (a) : (b))
int maxSubArray(int* nums, int numsSize) {
    int result = nums[0];
    int sum = 0;

    for(int i = 0; i < numsSize; i++){
        if(sum > 0)
            sum += nums[i];
        else
            sum = nums[i];
        result = MAX(result, sum);
    }

    return result;
}

至于进阶的分治算法, 目前还没想到O(n)复杂度的情况, 欢迎补充!

本文分享自微信公众号 - 程序员的碎碎念(gh_53e607dd4782)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-21

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 每日一题169: 求众数

    给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

    benny
  • Leetcode力扣算法题目——四数的和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    benny
  • 第三方平台代小程序(公众号)业务常见错误

    不要问我为什么知道这么多,全都是踩过的坑。如果您还遇到别的坑,请下方留言,来帮帮孩子

    benny
  • 每日算法系列【LeetCode 719】找出第 k 小的距离对

    给定一个整数数组,返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。

    godweiyang
  • Array - 16. 3Sum Closest

    Given an array nums of n integers and an integer target, find three integers in ...

    用户5705150
  • LeetCode 259. 较小的三数之和(固定一点,内层双指针)

    给定一个长度为 n 的整数数组和一个目标值 target,寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组...

    Michael阿明
  • LeetCode 18. 四数之和(双指针)

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

    Michael阿明
  • Leetcode 456. 132 Pattern

    Tyan
  • LeetCode 第 186 场周赛(1060/3107,前34.1%)

    全国排名:1060 / 3107,34.1%;全球排名:4145 / 11687,35.5%

    Michael阿明
  • 程序员面试金典 - 面试题 16.24. 数对和(双指针/哈希map)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/pairs-with-sum-lcci 著作权归领扣...

    Michael阿明

扫码关注云+社区

领取腾讯云代金券