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

leetcode.png

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

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

题目

给定一个整数数组 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

image.png

C实现

C语言实现上, 我使用了#define MAX 来比较两数的最大值, 代替了直接使用三目运算符的做法, 从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;
}

结果