考慮當前位置如果是一個負數的話，那么我們希望以它前一個位置結尾的某個段的積也是個負數，這樣就可以負負得正，并且我們希望這個積盡可能「負得更多」，即盡可能小。如果當前位置是一個正數的話，我們更希望以它前一個位置結尾的某個段的積也是個正數，并且希望它盡可能地大。于是這里我們可以再維護一個$f_{min}(i)$，它表示以第$i$個元素結尾的乘積最小子數組的乘積，那么我們可以得到這樣的動態規劃轉移方程：

import java.util.*;/*** @author longyy* @version 1.0*/
class Solution79 {public int maxProduct(int[] nums) {// 定義：dp[i]表示以下標為i的連續子數組最大乘積，dp[n]；dp_helper[i]表示以下標為i的連續子數組最小乘積// dp_helper[i](應對兩個負數乘積更大的情況)// 初始狀態：dp[0]=nums[0] dp_helper[0]=0// 狀態轉移方程：dp[i] = Math.max(dp[i-1],dp[i-1]*nums[i],dp_helper[i-1]*nums[i])//             dp_helper[i] = Math.min(dp_helper[i-1],dp[i-1]*nums[i],dp_helper[i-1]*nums[i])int n = nums.length;int[] dp = new int[n]; // db[i]表示以i結尾的最大的非空連續int[] dp_helper = new int[n]; // db[i]表示以i結尾的最小的非空連續dp[0] = nums[0];for (int i = 1; i < n; i++) {dp[i] = Math.max(Math.max(nums[i], nums[i] * dp[i - 1]), nums[i]*dp_helper[i-1]);dp_helper[i] = Math.min(Math.min(nums[i], nums[i]*dp_helper[i-1]), nums[i]*dp[i-1]);}return Arrays.stream(dp).max().getAsInt();}public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int[] nums = new int[n];for(int nums_i=0; nums_i < n; nums_i++){nums[nums_i] = in.nextInt();}Solution79 solution79 = new Solution79();System.out.println(solution79.maxProduct(nums));}
}