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.
Solution1: (Dynamic Programming)
MaxSum={A[i],ri−1+A[i]}
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
CurrentSum = nums[0]
MaxSum = nums[0]
for i in range(1, len(nums), 1):
if nums[i] + CurrentSum > nums[i]:
CurrentSum = nums[i] + CurrentSum
else:
CurrentSum = nums[i]
if CurrentSum > MaxSum:
MaxSum = CurrentSum
return MaxSum
Solution2:
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
self.nums = nums
return self.findmax(0, len(nums)-1)
def findmax(self, start, end):
if start == end:
return self.nums[start]
mid = (start + end)/2
maxleft = self.findmax(start, mid)
maxright = self.findmax(mid+1, end)
maxmid = self.nums[mid]
current = self.nums[mid]
for i in range(mid-1, start-1, -1):
current += self.nums[i]
if current > maxmid:
maxmid = current
current = maxmid
for i in range(mid+1, end+1, 1):
current += self.nums[i]
if current > maxmid:
maxmid = current
return max(maxleft, maxmid, maxright)
