使用Kadanes算法得到最大產品子陣列的範圍

Question

應用Kadane算法得到最大產品子陣列似乎很棘手。雖然我能夠獲得最大產品，但我並沒有真正獲得最大產品子陣列的正確範圍。

http://www.geeksforgeeks.org/maximum-product-subarray/解釋了獲得最大產品的方式，但我沒有得到我們如何得到子陣列的範圍。

有人能幫我理解範圍問題嗎？這是一個標準的面試問題，我想確保我理解產品案例的邏輯，而不是僅僅說可以修改最大總和子數組來回答最大產品子數組情況。

謝謝!!

Answer 1

您提供的鏈接似乎假設所有元素都是正面的。但在我看來，這不是一個安全的假設。我有返回代碼來獲取最大產品的子數組。我已經使用了Kadane's算法中使用的相同邏輯。代碼似乎適用於我的各種輸入。請讓我知道是否有問題。

public static int[] getMaxSubArray(int []arr){ 

    int maxEndingHere = arr[0], maxSoFar = arr[0], startIndex =0, start =0,end=0; 

    for(int i=1;i<arr.length;i++){ 

     if(maxEndingHere<0){ 
      maxEndingHere = arr[i]; 
      startIndex = i;   
     }else{   
      maxEndingHere *= arr[i]; 
     }   
     if(maxEndingHere>=maxSoFar){ 
      maxSoFar = maxEndingHere; 
      start = startIndex; 
      end = i; 
     } 
    }  
    if(start<=end) 
     return Arrays.copyOfRange(arr, start, end+1); 

    return null; 
} 

1. 樣品輸入= {6, 3, -10, 0, 2} 輸出= {6,3}
2. 樣品輸入= {-2,1,-3,4,-1,2,1,-5,4} 輸出= {4}
3. 樣品輸入= {-1,-2,-9,-6} 輸出= {-1}

Answer 2

def max_subarray(A): 
    max_ending_here = max_so_far = 0 
    max_start = start = 0 
    max_end = end = 0 

    # the range is [max_start, max_end) 

    for i, x in enumerate(A): 
     if max_ending_here + x > 0: 
      max_ending_here = max_ending_here + x 
      end = i+1 
     else: 
      max_ending_here = 0 
      start = end = i 

     if max_ending_here > max_so_far: 
      max_so_far = max_ending_here 
      max_start = start 
      max_end = end 

    return (max_start, max_end) 

Answer 3

它有三個基本情況：

1. 當前號碼+已經
2. 當前數目爲-ve
3. 當前數目爲0

你需要有兩個變量：

• min持有最小值至今

• max持有最大值至今。

現在對於case 3min和max將被重置爲1。

對於case 1：max將max * a[i]和min將是min*a[i]和1.

最小對於case 2：max將最大的a[i] * min和1，但min值將是max * a[i].

下面是代碼：

private static int getMaxProduct(int[] a){ 
    int minCurrent = 1, maxCurrent = 1, max = Integer.MIN_VALUE; 
    for (int current : a) { 
     if (current > 0) { 
      maxCurrent = maxCurrent * current; 
      minCurrent = Math.min(minCurrent * current, 1); 
     } else if (current == 0) { 
      maxCurrent = 1; 
      minCurrent = 1; 
     } else { 
      int x = maxCurrent; 
      maxCurrent = Math.max(minCurrent * current, 1); 
      minCurrent = x * current; 
     } 
     if (max < maxCurrent) { 
      max = maxCurrent; 
     } 
    } 
    //System.out.println(minCurrent); 
    return max; 
}