FilesExpand file tree

 master

/

53.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

24 lines (22 loc) · 754 Bytes

 master

/

53.py

Copy path

Top

File metadata and controls

• Code
• Blame

24 lines (22 loc) · 754 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Solution:

def maxSubArray(self, nums):

"""

68ms

13.6 MB

"""

n = len(nums)

if n == 0:

return 0

# 这里可以直接使用nums，为了方便我更好的可读使用了dp

# dp：已当前i为末尾的序列最大序列和

# 转移方程：dp[i] = max(nums[i], nums[i] + dp[i-1])

# 解释，以i为结尾有两种情况 [nums[i]], [...nums[i-1], nums[i]]

dp = [0] * n

max_sum = nums[0]

dp[0] = nums[0]

for i in range(1, n):

dp[i] = max(nums[i], nums[i] + dp[i-1])

max_sum = max(dp[i], max_sum)

return max_sum

s = Solution()

s.maxSubArray([-2,1,-3,4,-1,2,1,-5,4])