152. Maximum Product Subarray

給定一個整數數列nums，返回其中乘積最大的子數列。

https://leetcode.com/problems/maximum-product-subarray/

範例
Input: nums = [2,3,-2,4]
Output: 6 (因為[2,3]的乘積最大)

可以先參考這題，使用的方法相當類似。

使用相同的方法
從短數列[a,b,c,d]來看，我們要遍歷所有組合的話，方式如下

[a]

[a]
[a,b]
[b]

[a]
[a,b]
[b]
[a,b,c]
[b,c]
[c]

[a]
[a,b]
[b]
[a,b,c]
[b,c]
[c]
[a,b,c,d]
[b,c,d]
[c,d]
[d]

白字與紅字為所有子數列的組合，我們只要求出最大組合的即為解。
以這兩個區塊來討論，我們能觀察到兩件事

1. 紅字數列進入下一個組合時，會變為白字。
2. 紅字數列會和下一個整數組成新的數列。

秉持1. 這個規則，可知道「保留紅字曾出現過的最大值」即為解答。
但其中有陷阱，乘法要考慮負數，現在最小的負數也有可能反轉變為最大值。

因此紅字的最大值最小值都必須保留。

而紅字部分在乘入新整數時，會產生三種結果需比較

1. 極大值與新整數相乘
2. 極小值與新整數相乘
3. 新整數本身

若出現新的極大值或極小值，我們只要將其更新即可。

	public int maxSubArray(int[] nums) {
		// 白字部分
		int answer = nums[0];

		int red_max = nums[0];
		int red_min = nums[0];

		for (int i = 1, tmpA, tmpB; i < nums.length; i++) {

			// 紅字部分數值相乘後的最大最小值
			tmpA = red_max * nums[i];
			tmpB = red_min * nums[i];

			// 將相乘後的值，和本次的整數相比，取出最大和最小
			red_max = Math.max(tmpA, Math.max(tmpB, nums[i]));
			red_min = Math.min(tmpA, Math.min(tmpB, nums[i]));

			// 與白字相比，若出現最大值，則替換
			answer = Math.max(red_max, Math.max(red_min, answer));

		}
		return answer;
	}