Maximum sum sub-array

-

 


Comments

Post a Comment

Popular posts from this blog

Maximum Unsorted Subarray Asked in: Amazon Microsoft

-
Image
  You are given an array (zero-indexed) of   N   non-negative integers,   A 0 ,   A 1   ,…,   A N-1 . Find the minimum sub-array  A l ,  A l+1 ,…,  A r  so if we sort(in ascending order) that sub-array, then the whole array should get sorted. If  A  is already sorted, output  -1 . Example : Input 1: A = [1, 3, 2, 4, 5] Return: [1, 2] Input 2: A = [1, 2, 3, 4, 5] Return: [-1] In the above example(Input 1), if we sort the subarray  A 1 ,  A 2 , then whole array  A  should get sorted. ut Solution: class Solution:     # @param A : list of integers     # @return a list of integers     def subUnsort(self, A):         s_a=sorted(A)         if A==s_a:             return [-1]         l=len(A)         minI=-1         maxI=l       ...
Read more

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

-
Image
  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:       ...
Read more