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

#!/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_max 
        return max_sofar
        """
        :type nums: List[int]
        :rtype: int
        """

Comments

Best Programming language for machine learning.

Popular posts from this blog

Hackerrank - Dynamic Programming - The Coin Change Problem

Hackerrank - Implementation - Picking Numbers