最大子序列產品特例

我正在嘗試編寫一個基於遞歸解決方案的最大子序列總和程序（也就是它將遵循相同格式）的最大子序列產品程序。最大子序列產品特例

它至今在除結果應該爲'0'的所有情況下都有效，表明序列內沒有產品是肯定的。對於我下面五個序列，它適用於所有，但最後一個：

sequence1 = new int[]{-2, 5, 4, 4}; 
sequence2 = new int[]{6, 5, 0, -3, -5, -3, 7}; 
sequence3 = new int[]{0, -1, 1, 5, 0, -3, -4}; 
sequence4 = new int[]{0, 3, 3}; 
sequence5 = new int[]{0, -3, 3};

這裏是遞歸的方法，其中一個是序列，P1是[0]開始和P2是[最後一個索引] ：

public static int msp3(int[] a, int p1, int p2) { 

    if (p1 == p2) { 
     if (a[p1] != 0) { 
      maxprod = a[p1]; 
     } else { 
      maxprod = 0; 
     } 

    } else { 
     int m = (p1 + p2)/2; 

     int L = msp3(a, p1, m); 
     int R = msp3(a, m + 1, p2); 

     int prodlt = 1, prodrt = 1, PL = 0, PR = 0; 

     int checkForSplit = 0; 

     for (int i = m; i >= p1; i--) { 

      if (a[i] != 0) { 
       prodlt = prodlt * a[i]; 

       if (prodlt > PL) { 
        PL = prodlt; 
       } 
      } else { 
       if (i == m) { 
        prodlt = 1; 
        checkForSplit = 1; 
       } 
      } 
     } 

     for (int i = m + 1; i <= p2; i++) { 
      if (a[i] != 0) { 
       prodrt = prodrt * a[i]; 

       if (prodrt > PR) { 
        PR = prodrt; 
       } 
      } else { 
       if (i == m + 1) { 
        prodrt = 1; 
        checkForSplit = 1; 
       } 
      } 
     } 

     if (checkForSplit == 0) { 
      maxprod = max3(L, R, PL * PR); 
     } else { 
      maxprod = max3(L, R, PL); 
      maxprod = max(maxprod, PR); 
     } 

    } 
    return maxprod; 
}

約的說明「checkForSplit，」的值是0，除非A [1] == 0，並且我們檢查在當前子序列的左邊或最右邊的索引，在這種情況下，它被設置爲1這觸發了一個不同於PL乘以PR的'max3'的計算，其邏輯是如果PL或PR中的一個爲0，則可能兩個中的另一個不是，在這種情況下它們不應該是相乘。

正如我所說，這個算法適用於除第5個序列以外的所有算法。

任何想法？

來源

2014-09-22 user1837165

空集的產品是1，不是0。所以，如果你是真正做類似的問題，產品不能低於1

你實際上是試圖解決的問題，因此更好描述爲「具有2個或更多個成員的子序列的最大產品」。爲了解決這個問題，試着想出一個遞歸函數，該函數採用序列和範圍，並返回4個數字：

最小元素。
最大元素。
2個或更多元素的最小值。
2個或更多元素的最大值。

2個元素部分和3個元素部分的情況需要作爲明顯的特殊情況進行編碼。

對於遞歸步驟，最小和最大元素的邏輯是顯而易見的。最小和最大的產品將是這4個數字中的一個的8個可能產品的最小值和最大值，一邊是這4個數字中的一個。

來源

2014-09-23 12:48:52 btilly

最大子序列產品特例

回答

相關問題