Question
Given an array, find the continuous sub-array which have the maximum multiplication.
Similar Questions
- Easy - 53. Maximum Subarray
- Easy - 198. House Robber
- Medium - 238. Product of Array Except Self
- Easy - 628. Maximum Product of Three Numbers
- Medium - 713. Subarray Product Less Than K
Solution
We first define an array dpMax
, and use dpMax[i]
to denote the value of the largest product with the sub-array ending with the i-th element, that is, this array must contain the i-th element.
Then dpMax[i]
has several possible values:
- When
nums[i] >= 0
anddpMax[i-1] > 0
,dpMax[i] = dpMax[i-1] * nums[i]
- When
nums[i] >= 0
anddpMax[i-1] < 0
, if it is multiplied by the previous number, it will become a negative number, sodpMax[i] = nums[i]
- When
nums[i] < 0
, if the previous multiplication result is a large negative number, it will become a larger number if it is multiplied with the current negative number. So we also need an arraydpMin
to record the the smallest product value with sub-array ending in the i-th element, .- When
dpMin[i-1] < 0
,dpMax[i] = dpMin[i-1] * nums[i]
- When
dpMin[i-1] >= 0
,dpMax[i] = nums[i]
- When
Of course, how to find dpMin
is actually the same as the process of finding dpMax
above.
According to the above analysis, we need to have a lot of if else to determine different situations, here we can use a trick.
We noticed that the values of dpMax[i]
above are nothing more than three types
dpMax[i-1] * nums[i]
dpMin[i-1] * nums[i]
nums[i]
So when we update, we don’t need to distinguish the current situation, we only need to choose the largest one from the three values:
1 | dpMax[i] = max(dpMax[i-1] * nums[i], dpMin[i-1] * nums[i], nums[i]); |
The same applis for dpMin[i]
:
1 | dpMin[i] = min(dpMax[i-1] * nums[i], dpMin[i-1] * nums[i], nums[i]); |
Also notice that when updating dp[i]
, we only used dp[i-1]
, and the previous information would not be used. So we don’t need an array at all, we just need a variable to repeat overwrite and update.
1 | public int maxProduct(int[] nums) { |