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;
}
结果
