如何計算陣列的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.轉載