Leetcode最大和最小子序和

最大子序和，动态规划时间复杂度为O(n)，则假设每一步为step，
$$sf(x_1)=x_1$$

s f ( x 2 ) = { s f ( x 1 ) + x 2 , s f ( x 1 ) + x 2 > x 2 x 2 , s f ( x 1 ) + x 2 < = x 2 sf (x_2 ) = \left\{

s f ( x 3 ) = { s f ( x 2 ) + x 3 , s f ( x 2 ) + x 3 > x 3 x 3 , s f ( x 2 ) + x 3 < = x 3 sf (x_3 ) = \left\{

$$f(x_1,x_2)=max(sf(x_1),sf(x_2))$$

$$f(x_1,x_2,x_3)=max(sf(x_1),sf(x_2),sf(x_3))$$

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0

        global_max = nums[0]
        step_max = nums[0]

        if len(nums) == 1:
            return global_max

        for i in range(1, len(nums)):
            if step_max + nums[i] < nums[i]:
                step_max = nums[i]
            else:
                step_max += nums[i]

            if step_max > global_max:
                global_max = step_max

        return global_max


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
 

class Solution:
    def minSubArray(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0

        global_min = nums[0]
        step_min = nums[0]

        if len(nums) == 1:
            return global_min

        for i in range(1, len(nums)):
            if step_min + nums[i] < nums[i]:
                step_min += nums[i]
            else:
                step_max = nums[i]

            if step_min < global_min:
                global_min = step_min

        return global_min

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

https://www.zhihu.com/question/23995189/answer/35324479
https://www.zhihu.com/question/52165201

文章来源: blog.csdn.net，作者：herosunly，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/herosunly/article/details/106641003