iT邦幫忙

DAY 18
1

連續30天,挑戰演算法系列 第 18

[Day18] 30 天挑戰演算法 - 尋找最大(乘)積

題目來源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;
}

這次果然對了!!


上一篇
[Day17] 30 天挑戰演算法 - 萬用字元配對
下一篇
[Day19] 30 天挑戰演算法 - 數數字
系列文
連續30天,挑戰演算法30

尚未有邦友留言

立即登入留言