如何计算阵列的M个元素的最大产物与N个元素
问题是 鉴于整数数组和长度L,发现长度为L的子阵列使得所有整数的产品是最大的。 实施例: 输入:{4,1,-7,-8,9},3 输出:{-7,-8,9-}如何计算阵列的M个元素的最大产物与N个元素
我写了一个很粗地和逻辑地有缺陷的代码,其不给任何合理的输出。也许有人可以指向我在正确的方向
public class ProductProblem {
/*
* Given an array of integers and a length L, find a sub-array of length L such that the products of all integers are the biggest.
Example:
Input: {4, 1, -7, -8, 9}, 3
Output: {-7,-8,9}
*/
int a[];
int l;
int maxProduct;
public int findProduct(int[] input, int len,int product){
int[] output=new int[len];
for (int i=0;i<input.length;i++){
if(len>=1){
System.out.println(product);
System.out.println("input[i]="+input[i]);
product= product*input[i];
findProduct(input,len-1,product);
System.out.println("len="+len);
}
else {
return product;
}
}
if (product>maxProduct){
maxProduct=product;
}
return product;
}
public static void main(String[] args){
ProductProblem pp=new ProductProblem();
int[] a={1,3,-6,3,5};
pp.a=a;
int max=pp.findProduct(a,3,1);
System.out.println(max);
}
}
public int[] findProduct(int[] integers, int L) {
int maxProduct = Integer.MIN_VALUE;
int start = 0;
for (int i = 0; i + L < integers.length; i++) {
int tmp = 1;
for (int j = i; j < i + L; j++) tmp *= array[j];
if (tmp > maxProduct) {
maxProduct = tmp;
start = i;
}
}
int[] retVal = new int[L];
for (int i = start; i < start + L; i++) retVal[i - start] = integers[i];
return retVal;
}
这里的原理是,长度L(指定为方法参数L)的每个连续的子阵列的产物被记录时,与存储在最大产物一个变量。在函数结束时,重新创建并返回最大产品子数组。
您可以找到一组非连续的子阵列如下(然后找到最大的产品以类似的方式):
int[] subarrayL = new int[L];
public int[] findSubarrays(int[] integers, int L) {
for (int i = 0; i < L; i++) {
setSubarray(i, L);
}
}
public void setSubarray(int[] integers, int i, int L) {
for (int j = i; j < Math.min(integers.length, integers.length - L + i + 1); j++) {
subarrayL[i] = integers[j];
if (i + 1 < L) setSubarray(integers, i + 1, L);
}
}
如果子阵应该是连续的时候,我们就能在最终子阵列准时。下面的代码:
public int[] findProduct(int[] input, int L) {
if(L < input.length || L == 0) {
//invalid case
return 0;
}
int max_product = -2e9;
int result_start = 0;
int temp_result = 1;
for(int i = 0; i < L - 1; i++) {
temp_result *= input[i];
}
int left = 0;
for (int right = L - 1; right < input.length; right++) {
temp_result *= input[right];
if (temp_result > max_product) {
max_product = temp_result;
result_start = left;
}
temp_result /= input[left]; // removing the leftmost item as that will not be included in next sub array.
left ++;
}
int[] sub_array = new int[L];
for (int i = 0; i < L; i++) sub_array[i] = integers[result_start + i];
return sub_array;
}
它总是一个好主意,让一个高层次的描述/想法/的伪代码算法除了/而不是实际的代码。 – Dukeling
大多数语言允许通过数组值(或密钥值)排序,然后你可以切片阵列到顶部N个元素。
var array = sort(array)
var length = 10
var biggest = array_slice(array, 0, length);
对于像'1,2,-10,-200'这样的数组,'K = 2'怎么办? – Fallen
假设子集不一定是连续的,下面的算法可以解决它在O(N *日志(n))的时间,其中n是该阵列的长度。
关键的发现是,该解决方案必须由顶部2 * k个负数的,并且顶部L - 2枚* k个正数,对于k的一些值。
- 排序正数成阵列P,以降序
- 排序负数到数组N,降序绝对值顺序
- 特殊情况:如果P是空的,而L是奇数(意味着否定结果),从N的尾部返回L个项目。否则:分别
- 计算P和N,和存储在P上的累积产“和N”。即,P'[i] = P [1] * P [2] * ... * P [i]。设置P'[0] = N'[0] = 1。
- 环路上从0 k以L/2,并计算P '[L-2 * K] * N'[2 * K]。最大的结果对应于最佳子集,然后可以从P和N.转载
如果输入的所有元素均为零,则循环会超出范围。 – Victor
通过子阵你的意思是一个连续的子阵? – pkacprzak
哦拍我没有想到。我是假设它是不连续 – user3386479
问题的来源是这样的http://www.careercup.com/question?id=5752271719628800 – user3386479