如何在n个长度的数组中找到k个元素的最高乘积，其中k <ñ

本文介绍了如何在n个长度的数组中找到k个元素的最高乘积，其中k <ñ的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我最近尝试了3个元素的最高乘积的问题.现在，我正在尝试针对k个元素执行此操作.假设现在从3开始，它需要4个元素.我试图编写一个通用函数，以便它可以处理数组中的任何k个元素.算法必须位于O(n)中，就像具有3个元素的算法一样.

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 * val prod_2_low = low * val max_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 = 1 prod_low_minus_1 = 1 for 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_1 min_prod_n_1 = prod_high_minus_1 max_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 * val prod_low_minus_1 = low * val max_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

推荐答案

numpy 中的O(n)解决方案，在4个示例列表和@Stefan Pochmann的无情自动测试脚本中进行了压力测试.非常感谢Stefan，如果没有Stefan的投入，就会发现一些严重的错误.

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 def kmaxprod_v2(data, k): if len(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, therefore if 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 negative if 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 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 = 0 else: 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] if len(pos_high) == 0: snfp = 0 else: 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)

算法简述:

• 特殊情况k为奇数，所有数据为负，按分区找到k最小为负，返回prod，停止
• 按绝对值划分，并使用内省选择库功能在k-O(n)最坏情况下进行划分
• 如果prod top k> = 0，则停止
• 如果可能的话，将最小的正数内部交换为最大的负数外部，存储产品
• 如果可能，将最小的负数内部交换为最大的正数外部，请存储产品
• 返回上述最佳状态，停止

样品运行:

>>> 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

测试脚本，谢谢@Stefan Pochmann

Test script, thanks @Stefan Pochmann

import itertools, operator, functools, time def naive(data, k): return max(functools.reduce(operator.mul, comb) for comb in itertoolsbinations(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 += 1 print(data, k, a, b)