題目來源：Mximum Product Subarray

問題：
題目會給予一個陣列（最少會有一個元素），再從此陣列中尋找出含有最大（乘）積的相鄰子陣列。

例子
假設題目給予的陣列為：[2, 3, -2, 4]
則擁有最大積的相鄰陣列為 [2, 3], 其乘積為 6

若題目給的陣列只有一個元素: [-2]
則答案就是 -2

想法
關於這個題目，因為最大乘積的來源必須是相鄰的兩個元素，所以最直覺的想法就是：

• 如果只有一個元素，就直接回傳該元素
• 如果有兩個（含）元素以上，就兩兩相乘取最大值

有了想法，就來驗證一下對不對

兩兩相乘，取最大值回傳

public int FindMaxProduct(int[] array)
{
    if (array.Length == 1)
        return array[0];

    int maxProduct = 0;
    for (int i = 1; i < array.Length; i++)
    {
        int product = array[i - 1] * array[i];
        maxProduct = Math.Max(product, maxProduct);
    }
    return maxProduct;
}

沒想到，一驗證下居然出錯了。因為我們少考慮到一點，那就是

陣列有兩個元素，其中一個元素的值是 0。因為當輸入陣列為 [0, 2] 的時候，上面的程式碼會找出最大值 0 是錯的，實際的最大值是 2

沒錯，就是 0。這樣最大值當然是另一個元素阿！這題目實在是太賊了！好吧，那我們就多加一個判斷，如果鄰居是 0 我們就不理他！另外，由於有 0 的出現，所以單一個元素的值也要考慮，不然，在一個陣列中如果以這種情況排列 [0, 9, 0, -1, 0, 8] 不就又要出錯了！所以稍微修改一下程式碼，繼續進攻！

public int FindMaxProduct(int[] array)
{
    if (array.Length == 1)
        return array[0];

    int maxProduct = 0;
    for (int i = 1; i < array.Length; i++)
    {
        product = Math.Max(array[i], maxProduct);

        if (array[i - 1] == 0)
            product = array[i];
        else
            product = array[i - 1] * array[i];
    
        maxProduct = Math.Max(product, maxProduct);
    }
    return maxProduct;
}

驗證結果！又錯！！！什麼，還錯阿！

並且這次是錯在 當輸入陣列為 [-2, 3, -4] 其最大相鄰子陣列的乘積為 24。
這時後相信有認真看的人應該（或早就發現）發現問題點了！雖然題目給的範例是 兩個 元素相乘積，但是題目說了，是 子陣列 並沒有說是 一個或兩個元素 的乘積。
好吧！既然如此，這代表了題目要好好看，不要只看範例！因此我們必須重新檢視一下，要怎麼解這個題目。

首先，既然是 子陣列 ，所以什麼樣的子陣列乘積最大！ 既然是乘法，除了乘以 負數 或 0 之外，當然是越乘越大囉！但是 負數 很特別，因為他可以有逆轉勝的機會，當有兩個 負數 碰在一起，他就逆轉勝了！因此我們可以知道一個陣列能用 0 區隔出多個子陣列，但是別忘了 0 也有可能是最大數，所以：

既然在當陣列中全部都是正數時，我們可以用 0 來區隔子陣列，所以在每次計算最大積時，就必須在 乘積 與 目前元素 中取最大值，這目的是用來區隔 0，避免一遇到 0 後，後面的乘積全部都是 0。
例如 [1, 3, 0, 2, 5, 0, 3]`：
-> [i=1] 1 X 3 = 3
-> [i=2] 3 X 0 = 0
-> [i=3] 0 X 2 = 0
-> .... 通通是 0 了 ， 因為我們遇到 (豬隊友) 0 這個特別的數字

若是我們再 乘積 與 目前元素 之間取最大值，那就會是以下情況：
-> [i=0] current maxProduct = 1
-> [i=1] 1 X 3 = 3 max(3, 3) => 3
-> [i=2] 3 X 0 = 0 max(0, 3) => 3
-> [i=3] 0 X 2 = 0 max(0, 2) => 2
-> ... 遇到0時，可以捲土重來，我們的 目前最大乘積 不會在是 0 了

int currentMaxProduct = array[0];
int maxProduct = array[0];
for(int i=1; i<array.Length; i++)
{
    if ( array[i] >= 0  )
    {
        currentMaxProduct = Math.Max(currentMaxProduct * array[i], array[i]);
    }
  maxProduct = Math(maxProduct, currentMaxProduct);
}

那陣列中有負數出現時呢？ 那我們就必須多一個個變數 minProduct。因為當負數出現時，目前的最大乘積 若乘以負數，這時一定會變負的，但若乘以目前最小乘積（可能為負數）那他就可以持續的找到最大的正數（或目前最大的負數）。

for(int i=1; i<array.Length; i++)
{
    if (array[i] >= 0)
  {
      currentMaxProduct = Math.Max(currentMaxProduct * array[i], array[i]);
    currentMinProduct = Math.Min(currentMinProduct * array[i], array[i]);
  }
  else 
  {
      int temp = currentMaxProduct;
    // 因為此時的 array[i] 為負數，因此 currentMaxProduct 要乘以 currentMinProduct
    // 才有機會 負負 得正，若無法，就取最大的負數 array[i]
    currentMaxProduct = Math.Max(currentMinProduct * array[i], array[i]);
    currentMinProduct = Math.Min(temp * array[i], array[i]);
  }
  maxProduct = Math.Max(maxProduct, currentMaxProduct);
}

最後，讓我們根據上面的分析，整理一下程式碼，再進攻一次吧！

public int FindMaxProduct(int[] array)
{
    if (array.Length == 0)
        return 0;

    int currentMaxProduct = array[0];
    int currentMinProduct = array[0];
    int maxProduct = array[0];

    for (int i = 1; i < array.Length; i++)
    {
        if (array[i] >= 0)
        {
            currentMaxProduct = Math.Max(currentMaxProduct * array[i], array[i]);
            currentMinProduct = Math.Min(currentMinProduct * array[i], array[i]);
        }
        else
        {
            int temp = currentMaxProduct;
            currentMaxProduct = Math.Max(currentMinProduct * array[i], array[i]);
            currentMinProduct = Math.Min(temp * array[i], array[i]);
        }
        maxProduct = Math.Max(maxProduct, currentMaxProduct);
    }
    return maxProduct;
}

這次果然對了！！

• 如果你用 C＃ 可以利用我的 測試程式 來驗證
• 如果你用 Java or Python or C++ 可上 LeetCode Online Judge 驗證