FilesExpand file tree

 master

/

maximum-subarray.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

73 lines (59 loc) · 2.33 KB

 master

/

maximum-subarray.py

Copy path

Top

File metadata and controls

• Code
• Blame

73 lines (59 loc) · 2.33 KB

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

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

'''最大子序和

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

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/maximum-subarray

'''

'''

思路一：动态规划算法：将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。

参考：https://leetcode-cn.com/problems/maximum-subarray/solution/zheng-li-yi-xia-kan-de-dong-de-da-an-by-lizhiqiang/

时间复杂度：O(n)。

空间复杂度：O(1)。

'''

class Solution:

def maxSubArray(self, num):

res = num[0]

sum = num[0]

for i in range(1, len(num)):

if sum < 0:

sum = num[i]

else:

sum += num[i]

res = max(res, sum)

return res

'''

思路二：分治法。

参考：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode/

时间复杂度：O(nlogn)。

空间复杂度：O(logn)，递归时栈使用的空间。

'''

class Solution:

def cross_sum(self, nums, left, right, p):

if left == right:

return nums[left]

left_subsum = float('-inf')

curr_sum = 0

for i in range(p, left - 1, -1):

curr_sum += nums[i]

left_subsum = max(left_subsum, curr_sum)

right_subsum = float('-inf')

curr_sum = 0

for i in range(p + 1, right + 1):

curr_sum += nums[i]

right_subsum = max(right_subsum, curr_sum)

return left_subsum + right_subsum

def helper(self, nums, left, right):

if left == right:

return nums[left]

p = (left + right) // 2

left_sum = self.helper(nums, left, p)

right_sum = self.helper(nums, p + 1, right)

cross_sum = self.cross_sum(nums, left, right, p)

return max(left_sum, right_sum, cross_sum)

def maxSubArray(self, nums: 'List[int]') -> 'int':

return self.helper(nums, 0, len(nums) - 1)