Phonepe | OA Coding Questions and Solutions | 2022 | Set-19

Question

For proper oa or interview experiences list of all top tech companies visit :

https://oa.desiqna.in
https://interview.desiqna.in

Answer 1

Question 2
Given an array A of size n. Choose two non-intersecting subarrays (can be empty) such that total sum of elements of subarrays is maximum. Non-intersecting subarrays means no element is common between them.

 

Contraints

 

 1 <= N <= 10^3
 -10^9 <= Ai <= 10^9

 

Examples

 

 1) A = [-4,-5,-2] , sub1 = [], sub2 = [] , answer = sub1+sub2 = 0
 2) A = [5 -2 3 -6 5], sub1 = [5,-2,3] , sub2 = [5], answer = 11
 3) A = [-9,5,-9,-8,9,7,-10,10,9], sub1 = [9,7], sub2 = [10,9], answer = 35
 4) A = [1,2,3,4,5,6,7,8], sub1 = [1,2,3,4,5,6,7,8], sub2 = [], answer = 36

Answer 2

Second problem is just an application of kadane.
Store prefix and suffix max subarray sum.
prefix_max[i] denotes the maximum subarray sum uptil index i
suffix_max[i] denotes the maximum subarray sum starting from index >= i and uptil index n - 1 (0 based indexing)

 

Then finally iterate on indices from 0 to n - 2 and find the max value of (prefix[i] + suffix[i + 1])
ans = max(ans, prefix_max[i]+suffix_max[i + 1])
That will be your answer.

Answer 3

Kadane's O(n)

 

# https://leetcode.com/discuss/interview-question/2232666/phonepe-bengaluru/1469262
def maxSubArrSum2(A):
    def kadane(A):
        ret = [None] * (n + 1)
        ret[-1] = -inf
        cur = 0
        for i in range(len(A)):
            cur += A[i]
            cur = max(0, cur)
            ret[i] = max(ret[i - 1], cur)
        del ret[-1]
        return ret
    
    n = len(A)
    pf_max = kadane(A)
    sf_max = kadane(A[::-1])[::-1]
    ans = -inf
    for i in range(n - 1):
        ans = max(ans, pf_max[i] + sf_max[i + 1])
    return ans

A = [-4, -5, -2]; print(maxSubArrSum2(A))
A = [5, -2, 3, -6, 5]; print(maxSubArrSum2(A))
A = [-9, 5, -9, -8, 9, 7, -10, 10, 9]; print(maxSubArrSum2(A))
A = [1, 2, 3, 4, 5, 6, 7, 8]; print(maxSubArrSum2(A))
A = [3,-2,2,2,-2,1]; print(maxSubArrSum2(A))