LeetCode53

发表于 更新于 分类于 阅读次数： 本文字数： 809 阅读时长 ≈ 1 分钟
LeetCode53

LeetCode53

在这里插入图片描述
三种方法

1.暴力法

二重循环求出每个开头的最大的
在这里插入图片描述

2.分治法

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

class Solution:
    # Leetcode 53. Maximum Subarray
    # Divide And Conquer
    # N is the size of nums
    # Time Complexity: O(N)
    # Space Complexity: O(logN)
    def maxSubArray(self, nums: List[int]) -> int:
        return self.getMax(nums, 0, len(nums)-1)
    
    def getMax(self, nums, l, r):
        if l == r:
            return nums[l]
        mid = l + (r-l)//2
        leftSum = self.getMax(nums, l, mid)
        rightSum = self.getMax(nums, mid+1, r)
        crossSum = self.crossSum(nums, l, r)
        return max(leftSum, rightSum, crossSum)
    
    def crossSum(self, nums, l, r):
        mid = l + (r-l)//2
        # from mid to leftmost
        leftSum = nums[mid]
        leftMax = leftSum
        for i in range(mid-1, l-1, -1):
            leftSum += nums[i]
            leftMax = max(leftMax, leftSum)
        
        # from mid to rightmost
        rightSum = nums[mid+1]
        rightMax = rightSum
        for i in range(mid+2, r+1):
            rightSum += nums[i]
            rightMax = max(rightMax, rightSum)
        
        return leftMax + rightMax

3.动态规划

在这里插入图片描述

-------------本文结束感谢您的阅读-------------