未分類

Maximum Product Subarray

Array, DynamicProgramming, Go, LeetCode

Maximum Product Subarray

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

For example:

1
2
Given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
提示 解題應用
Array Array/Slice
DynamicProgramming 規律觀查

Default:

1
2
3
func maxProduct(nums []int) int {
}

解答思路:

之前有一篇Maximum Subarray是找出子陣列能組出的最大總合(其實就是每取出一個元素，如果目前的最大總合比取出元素小，就用該元素取代當作最大值陣列的開頭)，而這次則是要找出最大積合，兩者最大的差別是算總合只要找出最大值就好，而算積合除了找最大值也要一併找最小值，因為積合是由相乘而獲得，所以如果有負數存在，原本的最值在相乘後反而會變成最小值，反之原本最小值可能變為最大值，因此最後在求最大積合時，如果如果目前的最小積合比取出元素大就用該元素取代，同時目前的最大積合比取出元素小就用該元素取代，並每次都將目前的最大積合與最大值做比較，比最大值大就將其取代直到陣列遍歷結束才回傳最大值。

程式碼解說:

一開始先判斷陣列長度是否為0，如果是便回傳0回去，而如果陣列有元素存在，便直接取第一個值作為暫存的最小值與最大值，接著才開始從第二個元素開始取出直到陣列遍歷結束才回傳最大值

1
2
3
4
5
6
7
8
9
10
if len(nums) == 0 {
	return 0
}
tmpMin := nums[0]
tmpMax := nums[0]
max := tmpMax
for _, v := range nums[1:] {
...
}
return max

正如思路所述，由於最小值可能變為最大值，最大值可能變為最小值，因此在取出元素並兩兩相乘後，都先將結果存至另外的暫存變數，然後從兩暫存變數與取出的該元素值做比較找出最小值，再將其值取代暫存的最小值

1
2
3
4
5
6
7
8
9
10
11
var tmp1 int
var tmp2 int
tmp1 = tmpMin * v
tmp2 = tmpMax * v
if tmp1 <= tmp2 && tmp1 <= v {
	tmpMin = tmp1
} else if tmp2 <= tmp1 && tmp2 <= v {
	tmpMin = tmp2
} else {
	tmpMin = v
}

反之再從兩暫存變數與取出的該元素值做比較找出最大值，再將其值取代暫存的最大值，並每次都將暫存的最大值與最大值做比較，比最大值大就將其取代

1
2
3
4
5
6
7
8
9
10
if tmp1 >= tmp2 && tmp1 >= v {
	tmpMax = tmp1
} else if tmp2 >= tmp1 && tmp2 >= v {
	tmpMax = tmp2
} else {
	tmpMax = v
}
if tmpMax > max {
	max = tmpMax
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func maxProduct(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	var tmp1 int
	var tmp2 int
	tmpMin := nums[0]
	tmpMax := nums[0]
	max := tmpMax
	for _, v := range nums[1:] {
		tmp1 = tmpMin * v
		tmp2 = tmpMax * v
		if tmp1 <= tmp2 && tmp1 <= v {
			tmpMin = tmp1
		} else if tmp2 <= tmp1 && tmp2 <= v {
			tmpMin = tmp2
		} else {
			tmpMin = v
		}
		if tmp1 >= tmp2 && tmp1 >= v {
			tmpMax = tmp1
		} else if tmp2 >= tmp1 && tmp2 >= v {
			tmpMax = tmp2
		} else {
			tmpMax = v
		}
		if tmpMax > max {
			max = tmpMax
		}
	}
	return max
}

總結:

要從一陣列中找出子陣列能組出的最大積合，其做法是每當從陣列取出一個新值，如果如果目前的最小積合比取出元素大就用該元素取代，同時目前的最大積合比取出元素小就用該元素取代，並每次都將目前的最大積合與最大值做比較，比最大值大就將其取代直到陣列遍歷結束才回傳最大值。

分享到