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 a generic function so it could handle for any k elements within the array. The algo has to be in O(n) just like the one with 3 elements is.

 def highest_product_sol(input):high = max(input[0],input[1])low = min(input[0],input[1])max_prod_2 = input[0] * input[1]low_prod_2 = input[0] * input[1]max_prod_3 = max_prod_2 * input[2]prod_2_high = input[0] * input[1]prod_2_low = input[0] * input[1]for i in range(2,len(input)):val = input[i]max_prod_3 = max(max_prod_3,max_prod_2*val,low_prod_2*val)prod_2_high = high * valprod_2_low =  low * valmax_prod_2 = max(max_prod_2,prod_2_high)low_prod_2 = min(low_prod_2,prod_2_high)high = max(high,val)low = min(low,val)return (max_prod_2,low_prod_2,max_prod_3)def highest_product_num(input,num):high = max(input[0:num - 1])low = min(input[0:num - 1])print("max",high)print("min",low)prod_high_minus_1 = 1prod_low_minus_1 = 1for n in range(0,num-1):prod_high_minus_1 *= input[n]prod_low_minus_1 *= input[n]max_prod_n_1 = prod_high_minus_1min_prod_n_1 = prod_high_minus_1max_prod_n = prod_high_minus_1 * input[num-1]for i in range(num,len(input)):val = input[i]max_prod_n = max(max_prod_n,max_prod_n_1*val,min_prod_n_1*val)prod_high_minus_1 = high * valprod_low_minus_1 =  low * valmax_prod_n_1 = max(max_prod_n_1,prod_high_minus_1)min_prod_n_1 = min(min_prod_n_1,prod_low_minus_1)high = max(high,val)low = min(low,val)return max_prod_n
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]]
print(test_input)for i in test_input:print(highest_product_num(i,4),"\n")# correct `results`
# 1680
# 6000
# 600

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 npdef kmaxprod_v2(data, k):if len(data) < k:return np.nandata = np.asanyarray(data)# for integer dtypes convert to python ints to have unlimited range for the# final productdfp = 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, thereforeif len(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 == 1 and 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 elementap = np.argpartition(-np.absolute(data), k)low, high = ap[k:], ap[:k]# try multiplying the k with highest absolute valuegreedy = 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 outbpo = 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 highwni_ind = neg_high[wni_ind]spfn = bpo*np.prod(dfp[high[:wni_ind]])*np.prod(dfp[high[wni_ind+1:]])# bno in, wno outpos_high = np.where(~neg[high])[0]if len(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:]])return max(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)