Software Engineer

You are given an array 'arr' of length 'n', consisting of integers.

A subarray is a contiguous segment of an array. In other words, a subarray can be formed by removing 0 or more integers from the beginning and 0 or more integers from the end of an array.

Find the sum of the subarray (including empty subarray) having maximum sum among all subarrays.

The sum of an empty subarray is 0.

Example :

Input: 'arr' = [1, 2, 7, -4, 3, 2, -10, 9, 1]

Output: 11

Explanation: The subarray yielding the maximum sum is [1, 2, 7, -4, 3, 2].

Given two arrays ‘A’ and ‘B’ and an integer ‘C’, the task is to find the maximum possible length, say K, of the same indexed subarrays such that the sum of the maximum element in the K-length subarray in ‘B’ with the product between K and sum of the K-length subarray in ‘A’ does not exceed ‘C’.

More Formally you have to find the maximum length subarray, which starts and end at the same point in ‘A’ and ‘B’, and the sum of, maximum element of ‘B’ in that subarray, with the product of the length of the subarray and sum of a subarray in ‘A’ is less than or equal to ‘C’.

For example

Given:
‘N’ = 6, ‘C’ = 23
‘A’[] = {5, 19, 13, 2, 4, 0} 
‘B’[] = {10, 4, 7, 4, 5, 14}
The max-length subarray will be 2, consider the subarray from 3 to 4 (0-based indexing) and here, the subarray sum of ‘A’ = 6 max element in ‘B’ = 5. Therefore 6*2 + 5 = 17, Which is less than 23. Hence 2 is the final answer. 

If there are multiple answers, you can choose any subarray.