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)
更多推荐
Leetcode 53 Maximum Subarray
发布评论