iven 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.
My code:
class Solution:
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
result=self.recall(nums,0,len(nums)-1)
return result
def recall(self,nums,i,j):
if i==j:
return nums[i]
if i>j:
return -2339847982374932847892
sum_tmp=0
left_sum=0
m=int((i+j)/2)
for k in range(m-1,i-1,-1):
sum_tmp+=nums[k]
left_sum=max([left_sum,sum_tmp])
sum_tmp=0
right_sum=0
for k in range(m+1,j+1):
sum_tmp+=nums[k]
right_sum=max([right_sum,sum_tmp])
left=self.recall(nums,i,m-1)
right=self.recall(nums,m+1,j)
print('left %d, right %d, sum_tmp %d'%(left,right,left_sum+nums[m]+right_sum))
return max([left,right,left_sum+nums[m]+right_sum])