今天应该开始这一题了,题目如下:
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
解题思路如下: 把数组的值依次相加,正数的话会一直变大,但是如果出现了负数,就不是最大的了。 应该还有其他的解决方案,欢迎提供,我看了LeetCode的其他解决方案,还是有很多值得学习的。 代码:
# @File : maximum_subarray.py
# @Date : 2020-02-08
# @Author : shengjia
def maxSubArray(nums):
for i in range(1, len(nums)):
if nums[i - 1] > 0:
nums[i] += nums[i - 1]
print(max(nums))
return max(nums)
inputs = [-2, 1, -3, 4, -1, 2, 5, -5, 4]
maxSubArray(inputs)
有个大佬的解决如下,感觉还是很6的,鉴于我对python的浅陋(只会用python解一些简单的题),不能在这瞎比比了。
好了,今日营业到此为止,打烊了,晚安! 哦 顺便贴上佳爷练习的地址(https://github.com/ZoeSj/LeetCodeDay),感兴趣的可以一起学习,加油~