1、题目
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
2、我的解法
(1)超时的暴力解法
1 # -*- coding: utf-8 -*- 2 # @Time : 2020/2/6 22:15 3 # @Author : SmartCat0929 4 # @Email : 1027699719@qq.com 5 # @Link : https://github.com/SmartCat0929 6 # @Site : 7 # @File : 53. Maximum Subarray(超时的暴力算法）.py 8 from typing import List 9 10 11 class Solution: 12 def maxSubArray(self, nums: List[int]) -> int: 13 maxSum = -9999999999 14 if len(nums)>1: 15 maxSum = -99999 16 for i in range(0, len(nums)): 17 for j in range(i, len(nums)): 18 thisSum = sum(nums[i:j+1]) 19 if thisSum > maxSum: 20 maxSum = thisSum 21 return maxSum 22 elif len(nums)==1: 23 maxSum=nums[0] 24 return maxSum 25 else: 26 return 0 27 28 print(Solution().maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))
（2）局部最大值（copy大神）
1 # -*- coding: utf-8 -*- 2 # @Time : 2020/2/7 16:12 3 # @Author : SmartCat0929 4 # @Email : 1027699719@qq.com 5 # @Link : https://github.com/SmartCat0929 6 # @Site : 7 # @File : 53. Maximum Subarray.py 8 9 from typing import List 10 class Solution: 11 def maxSubArray(self, nums: List[int]) -> int: 12 n = len(nums) 13 tmp = 0 14 res = float(‘-inf‘) 15 for i in range(n): 16 if tmp < 0: 17 tmp = 0 18 tmp = tmp + nums[i] 19 res = max(res, tmp) 20 return res 21 print(Solution().maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))
LeetCode练题——53. Maximum Subarray
原文：https://www.cnblogs.com/Smart-Cat/p/12274281.html