[LeetCode] 152. Maximum Product Subarray

轉自LeetCode

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

<Solution>
這題是要找出有最大乘積的 subarray，回傳的答案回傳乘積就好

解題時要注意，會有 0 和負數的情況，想法如下

• prvMax 是指上一輪最大的乘積，如果沒有比 1 大，就設為 1

• 當數值大於零的時候，就是相乘

• 當數值小於等於零的時候，curMax = curMin * n，curMin = prvMax * n

• 每一次 iteration 結束，紀錄最大的乘積是多少

code 如下

相同思路，但不同的寫法

• 正數，直接相乘

• 負數，那麼原本最小的會變最大，最大變最小

• 遇到 0，保持之前的最大和最小

綜合上面，可以導出

max product = max( current max, current num, current min)
min product = min( current max, current num, current min)

code 如下(參考資料)