LeetCode No.53 | StriveZs的博客

LeetCode No.53

LeetCode第五十三题

自己代码的开源仓库:click here 欢迎Star和Folk :)

题目描述

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
示例 1

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

输入:nums = [1]
输出:1
示例 3

输入:nums = [0]
输出:0
示例 4

输入:nums = [-1]
输出:-1
示例 5

输入:nums = [-100000]
输出:-100000
 

提示:

1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int

核心思想: 1. 暴力法:遍历所有情况吧,采用适当的剪枝
2. 动态规划:突然想到可以采用动态规划的方法
"""
# 本题就采用动态规划的方法
dp = [0 for i in range(len(nums))]
dp[0] = nums[0]
result = dp[0]
for i in range(1,len(nums)):
dp[i] = max(dp[i-1]+nums[i],nums[i])
result = max(result,dp[i])
return result

if __name__ == '__main__':
s = Solution()
print(s.maxSubArray(nums = [1]))
StriveZs wechat
Hobby lead  creation, technology change world.