Max Sum Contiguous Sub array Asked in: Facebook PayPal Yahoo Microsoft LinkedIn Amazon Goldman Sachs

 Find the contiguous subarray within an array, A of length N which has the largest sum.

Input Format:

The first and the only argument contains an integer array, A.

Output Format:

Return an integer representing the maximum possible sum of the contiguous subarray.

Constraints:

1 <= N <= 1e6
-1000 <= A[i] <= 1000

For example:

Input 1:
    A = [1, 2, 3, 4, -10]

Output 1:
    10

Explanation 1:
    The subarray [1, 2, 3, 4] has the maximum possible sum of 10.

Input 2:
    A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output 2:
    6

Explanation 2:
    The subarray [4,-1,2,1] has the maximum possible sum of 6.
Solution:

we can use Kadane's Algo O(n) | O(1)

class Solution:
    # @param A : tuple of integers
    # @return an integer
    def maxSubArray(self, A):
        s=-(2**30)
        ans=0
        for i in A:
            ans+=i
            if s<ans:
                s=ans
            if ans<0:
                ans=0
        return s

ScreenShot:










Comments

Popular posts from this blog

Trouble with the Number System

Residue Arithmetic

Perfect Peak of Array