LeetCode - Maximum contiguous subarray sum
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
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
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
#!/bin/python def maxSubArray(self, a): cur_max = a[0] max_sofar = a[0] for k in range(1, len(a)): if cur_max < 0: cur_max = a[k] else: cur_max += a[k] if max_sofar < cur_max:#if current max increases than max so far, new max so far would be current max max_sofar = cur_maxreturn max_sofar """ :type nums: List[int] :rtype: int """
Comments
Post a Comment