CODEWITHSUNDEEP
algorithmdivide-and-conquersub-array
AMRO
AMRO

Reputation: 61

Max product in array of 2 elements

Given an array of positive numbers I need to find the maximum of the expression (j - i)*(b[j] + b[i]) where j and i are array indices. I tried using divide and conquer but in the merge step I could not find an efficient algorithm to combine the results of the left and right sub-arrays. The constraints on the length of the array is 1,000,000 (maximum array size), and time is 1 second. Your help is appreciated

Upvotes: 0

Views: 343

Answers (3)

גלעד ברקן
גלעד ברקן

Reputation: 23955

Expanding (j - i) * (b[j] + b[i]), we get:

j*b_j + j*b_i - i*b_j - i*b_i

which we can rewrite as the constant and vector dot product,

j*b_j + (j, -b_j, -1) ⋅ (b_i, i, i*b_i)

and then -- assuming all elements previous to the jth have been seen -- look for:

j*b_j + max((j, -b_j, -1) ⋅ (b_i, i, i*b_i))
  where i < j

Maximising the vector dot product can be achieved in log time with convex hull and farthest point query, although implementation is not trivial.

Upvotes: 0

Jerome
Jerome

Reputation: 354

Following the logic of Shridhar, i think that should works.

const arr = [1,3,5,2,3,6,89,2,13,45,67,7,8,9]

let left = 0 
let right = arr.length - 1 

let max = (left - right) * (arr[left] + arr[right])
right--
let ref = 0 
function algo(arr) {
        do {
                let sum = (left - right) * (arr[left] + arr[right])
                if (sum > max) max = sum 
                ref++
                if (ref % 2 === 0) right--
                else left++
                    
        } while(left < right)
            
        return max 
}

console.log(algo(arr))

Upvotes: 0

Shridhar R Kulkarni
Shridhar R Kulkarni

Reputation: 7063

Let us throw two pointers at the problem:

left = 0, right = length of array - 1
do{
    max_product = max(max_product, (right-left)*(array[left]+array[right]))
    if array[left] < array[right]:
        left++
    else
        right--
} while (left < right)

Time Complexity: O(size of array), Space Complexity: O(1)

As Abinav pointed out, the greedy selection of max on the left won't work. So, below solution won't work.

This is a dynamic programming based question. Maintain a dp array. dp[index] denotes index of max(array[0]...array[index-1]). So at every index you calculate

result = max(result, (index - dp[index]) * (array[dp[index]]+array[index])).

Time complexity: O(size of array), Space complexity: O(size of array)

Try if it is possible to reduce space to O(1) as an exercise.

Upvotes: 0

Related Questions