Leetcode 53 Maximum Subarray

Leetcode 53 Maximum Subarray"/>

Leetcode 53 Maximum Subarray

**Leetcode 53 Maximum Subarray

题目描述

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.

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路解析

• 暴力

class Solution:def maxSubArray(self, nums: List[int]) -> int:result = []length = len(nums)if length == 0:return 0if length == 1:return nums[0]for i in range(0, length):for j in range(i, length):result.append(sum(nums[i:j+1]))return max(result)        

时间复杂度 O ( n 2 ) O(n^2) O(n2)

• 动态规划

class Solution:def maxSubArray(self, nums: List[int]) -> int:length = len(nums)if length == 0:return 0if length == 1:return nums[0]dp = [0 for _ in nums]for i in range(length):dp[i] = max(nums[i], nums[i] + dp[i - 1])return max(dp)