Software Engineer

You are given two arrays of the positive integers. You are required to select two sub-arrays of equal length, one from each array, such that the sum of the OR of two sub-arrays is maximum. Your task is to return the maximum sum possible.

An array ‘C’ is a subarray of array ‘D’ if ‘C’ can be obtained from ‘D’ by deletion of several elements from the beginning and several elements from the end.

Example : let ‘arr’ = [1,0,0] then the possible subarrays of ‘arr’ will be- {1}, {0},{0},{1,0},{0,0},{1,0,0}.

For Example:

Let the first array be : ‘arr1’ = {1,5,8,4} and the second array be ‘arr2’ = {3,7,16,1}

For this, the maximum sum takes the sub-array {5,8} from the first ‘arr1’ and {7,16} from arrays, two, the OR sum will be 13 + 23 = 26, which is maximum.

You are given an array “A” of N integers. Your task is to find the maximum element in all K sized contiguous subarrays from left to right.

For Example:

If A = [3, 2, 3], and K = 2.
Then max of [3, 2] = 3 and max of [2, 3] = 3
So, the answer will be [3, 3]

If A = [3, 2, 3, 5, 1, 7] and K = 3.
Then max of [3, 2, 3] = 3 
Then max of [2, 3, 5] = 5 
Then max of [3, 5, 1] = 5 
Then max of [5, 1, 7] = 7 
So  the answer will be [3, 5, 5, 7]

Follow Up :

Can you solve the problem in O(N) time complexity and O(K) space complexity?