How To Find Highest Product Of K Elements In An Array Of N Length, Where K < N

I recently tried the question for the highest product of 3 elements. Now I am trying to do it for the k elements. Let's say from 3 now it is asking for 4 elements. I tried to write

Solution 1:

O(n) solution in numpy, stress-tested on the 4 example lists and @Stefan Pochmann's merciless auto test script. Big thanks to Stefan, without whose input a couple of severe bugs would have gone unnoticed.

import numpy as np

defkmaxprod_v2(data, k):
    iflen(data) < k:
        return np.nan
    data = np.asanyarray(data)
    # for integer dtypes convert to python ints to have unlimited range for the# final product
    dfp = data.astype(object) if data.dtype in (
        int, np.int64, np.int32, np.int16, np.int8) else data
    # np.argpartition raises an exception if len(data) == k, thereforeiflen(data) == k:
        return np.prod(dfp)
    neg = data <= 0# if k is odd and there are no positive elements we must settle for the# least negativeif k % 2 == 1and np.count_nonzero(neg) == len(data):
        return np.prod(-np.partition(-data, k)[:k].astype(dfp.dtype))
    # now n > k and we have at least one positive element
    ap = np.argpartition(-np.absolute(data), k)
    low, high = ap[k:], ap[:k]
    # try multiplying the k with highest absolute value
    greedy = np.prod(dfp[high])
    if greedy >= 0:
        return greedy
    # there are two possible ways of fixing the sign:# either swap the worst negative inside for the best positive outside# or swap the worst positive inside for the best negative outside# compute both and compare# bpo in, wni out
    bpo = np.max(dfp[low])
    if bpo <= 0:
        spfn = 0else:
        neg_high = np.where(neg[high])[0]
        wni_ind = np.argmax(data[high[neg_high]])
        # translate to index in high
        wni_ind = neg_high[wni_ind]
        spfn = bpo*np.prod(dfp[high[:wni_ind]])*np.prod(dfp[high[wni_ind+1:]])
    # bno in, wno out
    pos_high = np.where(~neg[high])[0]
    iflen(pos_high) == 0:
        snfp = 0else:
        wpi_ind = np.argmin(data[high[pos_high]])
        wpi_ind = pos_high[wpi_ind]
        bno = np.min(dfp[low])
        snfp = bno*np.prod(dfp[high[:wpi_ind]])*np.prod(dfp[high[wpi_ind+1:]])
    returnmax(spfn, snfp)

Brief description of algo:

• special case k odd, all data negative find k least negative by partition, return prod, stop
• partition by absolute value, splitting at rank k - O(n) worstcase with introselect library function
• if prod top k >= 0, stop
• if possible swap least positive inside for most negative outside, store prod
• if possible swap least negative inside for most positive outside, store prod
• return best of above, stop

Sample run:

>>>test_input = [[1,2,3,4,5,6,7,8],[1,-2,3,4,5,100,2,3,1],[-10,-10,1,3,2],[1000,7,-6,2,2]]>>>for t in test_input:...    kmp.kmaxprod(t,4)... 
1680
6000
600
28000

Test script, thanks @Stefan Pochmann

import itertools, operator, functools, time
def naive(data, k):
    return max(functools.reduce(operator.mul, comb) for comb in itertools.combinations(data, k))

test_input = [([1,2,3,4,5,6,7,8], 4), ([1,-2,3,4,5,100,2,3,1], 4),
              ([-10,-10,1,3,2], 4), ([1000,7,-6,2,2],4),
              ([-1, 0, 1], 2), ([2, 5, 8, 9, 1, 3, 7], 4),
              ([-1, -1, 2, 1], 2), ([-1000, -1, 2, 3], 2),
              ([3, 5, 2, 8, 3], 2), ([-1000, -1, 2, 3, 4, 5, 6, 7], 2)]

for t, k in test_input:
    print(t, k, kmaxprod_v2(t, k), naive(t, k))

ne = 0
t = np.zeros((3,))
import random
for k in range(2, 20):
  for n in range(k, 24):
    print('n =', n, ': k =', k, 'errors:', ne, 'total time O(n), naive:', np.diff(t))
    for _ in range(100):
        data = [random.randrange(-14, 15) for _ in range(n)]
        t[0] += time.time()
        a = kmaxprod_v2(data, k)
        t[1] += time.time()
        b = naive(data, k)
        t[2] += time.time()
        if a != b:
            ne += 1print(data, k, a, b)

Solution 2:

from functools import reduce
import operator

defget_largest_product(l,n):
    possible_products = [reduce(operator.mul,c,1) for c in combinations(l, n)]
    returnmax(possible_products)

print (get_largest_product([232,434,5,4],3))

Output:

503440