我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題原始碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 152. 乘積最大子陣列
題目
給你一個整數陣列 nums ，請你找出陣列中乘積最大的連續子陣列（該子陣列中至少包含一個數字），并回傳該子陣列所對應的乘積，
示例 1:
輸入: [2,3,-2,4]
輸出: 6
解釋: 子陣列 [2,3] 有最大乘積 6，
示例 2:
輸入: [-2,0,-1]
輸出: 0
解釋: 結果不能為 2, 因為 [-2,-1] 不是子陣列，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-product-subarray
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路
本題與以下題屬同類問題，思路相似，可對比學習：
- LeetCode 121. 買賣股票的最佳時機
- LeetCode 53. 最大子序和
思路1-與求最大連續和子陣列類似的思路
思路分析：求最大連續和子陣列因為是加法，對負數是直接放棄，但本題是乘法，乘積為負時若后面再遇到負數會轉為正數，所以關鍵點是如何處理乘積正負轉變的問題；
此外還有一個問題點：0值的處理；
思路是記錄連乘積的最大值與最小值，每當遇到負數時，將最大值與最小值互換，這樣解決了兩個問題:
- 連乘奇數個負數時，最值會互換，符號轉變，最值特性不變；
- 連乘偶數個負數時，最值等價于未互換，符號不變，最值特性不變；
- 每當遇到0時，最值均會重置為下一個非0數重新開始處理；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $
演算法原始碼示例
package leetcode;
/**
* @author ZhouJie
* @date 2020年5月18日 下午3:02:09
* @Description: 152. 乘積最大子陣列
*
*/
public class LeetCode_0152 {
}
class Solution_0152 {
/**
* @author: ZhouJie
* @date: 2020年5月18日 下午3:02:39
* @param: @param nums
* @param: @return
* @return: int
* @Description: 1-
*
*/
public int maxProduct_1(int[] nums) {
int max = 1, min = 1, result = Integer.MIN_VALUE;
for (int val : nums) {
// 最值初始化均為1，那么后續每遇到一次負數就將最值互換一次，保持最值的屬性不變；
if (val < 0) {
max = max ^ min;
min = max ^ min;
max = max ^ min;
}
// 求連乘到現在的最值，是與當前要乘的因子比較
max = Math.max(max * val, val);
min = Math.min(min * val, val);
// 記錄最終的最大值
result = Math.max(result, max);
}
return result;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/190352.html
標籤：Java
上一篇：Java-IO流學習