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.
题目地址: Maximum Subarray
难度: Easy
思路: 最大子序列和问题
代码:
class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ n = len(nums) tmp = 0 res = float(‘-inf‘) for i in range(n): if tmp < 0: tmp = 0 tmp = tmp + nums[i] res = max(res, tmp) return res
时间复杂度: O(n)
空间复杂度: O(1)
原文：https://www.cnblogs.com/chimpan/p/9733483.html