LeetCode_Note/python/Maximum-Subarray/Maximum-Subarray.py at master · bryceustc/LeetCode_Note · GitHub

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
### Solution 1：
classSolution:
defmaxSubArray(self, nums: List[int]) ->int:
res=nums[0]
n=len(nums)
foriinrange(n):
s=0
forjinrange(i,n):
s+=nums[j]
res=max(res,s)
returnres


### Solution 2：
classSolution:
defmaxSubArray(self, nums: List[int]) ->int:
res=nums[0]
s=0
n=len(nums)
foriinrange(n):
ifs>0:
s+=nums[i]
else:
s=nums[i]
res=max(res,s)
returnres


classSolution:
defmaxSubArray(self, nums: List[int]) ->int:
res=nums[0]
n=len(nums)
dp= [0for_inrange(n)]
dp[0] =nums[0]
foriinrange(1,n):
dp[i] =max(dp[i-1]+nums[i],nums[i])
res=max(res,dp[i])
returnres


### Solution 3：
classSolution:
defmaxSubArray(self, nums: List[int]) ->int:
n=len(nums)
#递归终止条件
ifn==1:
returnnums[0]
else:
#递归计算左半边最大子序和
max_left=self.maxSubArray(nums[0:len(nums) //2])
#递归计算右半边最大子序和
max_right=self.maxSubArray(nums[len(nums) //2:len(nums)])

#计算中间的最大子序和，从右到左计算左边的最大子序和，从左到右计算右边的最大子序和，再相加
max_l=nums[len(nums) //2-1]
tmp=0
foriinrange(len(nums) //2-1, -1, -1):
tmp+=nums[i]
max_l=max(tmp, max_l)
max_r=nums[len(nums) //2]
tmp=0
foriinrange(len(nums) //2, len(nums)):
tmp+=nums[i]
max_r=max(tmp, max_r)
#返回三个中的最大值
returnmax(max_right,max_left,max_l+max_r)


### Solution 4:
classSolution:
defmaxSubArray(self, nums):
# write code here
res=nums[0]
n=len(nums)
sum_num=0
fornuminnums:
ifsum_num>0:
sum_num+=num
else:
sum_num=num
res=max(res,sum_num)
returnres