Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array[-2,1,-3,4,-1,2,1,-5,4]
,
the contiguous subarray[4,-1,2,1]
has the largest sum =6
.
URL: https://leetcode.com/problems/maximum-subarray/
import sys
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums == []:
return 0
elif len(nums) == 1:
return nums[0]
elif len(nums) == 2:
return max(nums[0], nums[1], nums[0]+nums[1])
else:
all_neg = True
for entries in nums:
if entries >= 0:
all_neg = False
if all_neg == False:
curr_sum = 0
max_sum = - sys.maxsize - 1
for i in range(len(nums)):
curr_sum += nums[i]
if curr_sum < 0:
curr_sum = 0
if curr_sum > max_sum:
max_sum = curr_sum
return max_sum
else:
return max(nums)