1. 题目描述
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
翻译过来就是求最大乘积子序列的乘积。
2. 解题思路
- 定义当前状态的最大乘积，最小乘积，返回结果。
- 下一个时刻的最大乘积，就是 下个时刻的值，当前最大值*下个时刻值，当前最小值 * 下个时刻的的值， 这三个中间的最大值。
- 下个时刻的最小值为 下个时刻的值，当前最大值*下个时刻值，当前最小值 * 下个时刻的的值， 这三个中间的最小值。
- 若最大值大于返回结果，返回结果 = 最大值
- 返回计算结果。
3. 代码
代码语言：javascript复制
class Solution {
public int maxProduct(int[] nums) {
int result = nums[0];
int max = nums[0];
int min = nums[0];
for(int i = 1; i < nums.length; i ) {
int maxTemp = max;
max = Math.max(nums[i], Math.max(nums[i] * min, nums[i] * max));
min = Math.min(nums[i], Math.min(nums[i] * min, nums[i] * maxTemp));
if (max > result) {
result = max;
}
}
return result;
}
}
