0 like 0 dislike
1,077 views
For proper oa or interview experiences list of all top tech companies visit :

https://oa.desiqna.in
https://interview.desiqna.in
| 1,077 views

0 like 0 dislike

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``````
by Expert (46,090 points)
0 like 0 dislike
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])
by Expert (46,090 points)
1 like 0 dislike

``````# https://leetcode.com/discuss/interview-question/2232666/phonepe-bengaluru/1469262
def maxSubArrSum2(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)