如何计算阵列的M个元素的最大产物与N个元素

Question

问题是 鉴于整数数组和长度L，发现长度为L的子阵列使得所有整数的产品是最大的。 实施例： 输入：{4,1，-7，-8，9}，3 输出：{-7，-8,9-}

我写了一个很粗地和逻辑地有缺陷的代码，其不给任何合理的输出。也许有人可以指向我在正确的方向

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); 
    } 
} 

Answer 1

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); 
    } 
} 

Answer 2

如果子阵应该是连续的时候，我们就能在最终子阵列准时。下面的代码：

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

Answer 3

大多数语言允许通过数组值（或密钥值）排序，然后你可以切片阵列到顶部N个元素。

var array = sort(array) 
var length = 10 
var biggest = array_slice(array, 0, length); 

Answer 4

假设子集不一定是连续的，下面的算法可以解决它在O（N *日志（n））的时间，其中n是该阵列的长度。

关键的发现是，该解决方案必须由顶部2 * k个负数的，并且顶部L - 2枚* k个正数，对于k的一些值。

1. 排序正数成阵列P，以降序
2. 排序负数到数组N，降序绝对值顺序
3. 特殊情况：如果P是空的，而L是奇数（意味着否定结果），从N的尾部返回L个项目。否则：分别
4. 计算P和N，和存储在P上的累积产“和N”。即，P'[i] = P [1] * P [2] * ... * P [i]。设置P'[0] = N'[0] = 1。
5. 环路上从0 k以L/2，并计算P '[L-2 * K] * N'[2 * K]。最大的结果对应于最佳子集，然后可以从P和N.转载