CODEWITHSUNDEEP
pythonalgorithmperformancemaxproduct
Deadjam106
Deadjam106

Reputation: 11

Looking to speed up this max pairwise product

I'm very new to programming, so please go easy on me :)

How can I make the following python code output quicker-

n = int(input())
a = [int(x) for x in input().split()]
assert(len(a) == n)

result = 0

for i in range(0, n):
    for j in range(i+1, n):
        if a[i]*a[j] > result:
            result = a[i]*a[j]

print(result)

What are some options to maximize its speed?

Upvotes: 1

Views: 1262

Answers (5)

Everton Carneiro
Everton Carneiro

Reputation: 121

I came up with this O(n) solution:

def maxPairwise(l):
   if len(l) == 2:
       return l[0]*l[1]
   elif len(l) == 1:
       return l[0]
   else:
       max1 = 0
       max2 = 0
       for i in l:
           if i > max1:
               max1 = i
           if i > max2 and i != max1:
               max2 = i
       return max1 * max2

Upvotes: 0

shining
shining

Reputation: 1069

My solution would use sorted and set,as this algorithm work on duplicate items as well.

    x, y = sorted(set(nums))[-2:]
    print(x * y)

Upvotes: 0

mveith
mveith

Reputation: 1

I see, Stepik.org course lesson "Maximum pairwise product":

Try the following, instead of the cascaded for-loop:

n1 = max(a)
a.remove(n1)
result = n1*max(a)

Which essentially saves the biggest value in a variable, removes it from the sequence, and multiplies it with the now biggest value of the sequence (2nd biggest value in the original sequence).

Upvotes: 0

hilberts_drinking_problem
hilberts_drinking_problem

Reputation: 11602

You are trying to compute the maximal product of distinct integers in a list. Computing product for every pair has O(N^2) time complexity.

You can reduce this to O(N log(N)) by sorting the list.

a = sorted(a)
ans = max(a[0] * a[1], a[-2] * a[-1])

You can further improve this to linear time, but I will let you figure it out.

Upvotes: 0

Salvador Dali
Salvador Dali

Reputation: 222811

All you are trying to do is to find two different elements whos product is the biggest. This happens when two numbers are the biggest. So you basically have find two biggest numbers in the array. This can be done in O(n).

One example how this can be done. Find the biggest number and it's position. Save it, remove it and find the max of the result (which will be second biggest). Now multiply both.

Upvotes: 2

Related Questions