78 lines
2.4 KiB
Markdown
78 lines
2.4 KiB
Markdown
|
- Leetcode Maximum Product Subarray
|
||
|
|
id:: 64261f45-6885-422c-808c-9344273af1d4
|
||
|
|
collapsed:: true
|
||
|
|
|
||
|
|
- Times:
|
||
|
|
- Completion time: 08:38
|
||
|
|
- Revisions:
|
||
|
|
- Tags:
|
||
|
|
- Algorithms: #Kadane_s_algorithm
|
||
|
|
- Data structures: #array
|
||
|
|
- Difficulty: #difficulty_easy
|
||
|
|
- Platforms: #leetcode
|
||
|
|
- Links:
|
||
|
|
- [link to the problem](https://leetcode.com/problems/maximum-product-subarray/description/)
|
||
|
|
- Problem:
|
||
|
|
- Given an integer array `nums`, find a subarray that has the largest product, and return _the product_. The test cases are generated so that the answer will fit in a **32-bit** integer.
|
||
|
|
- Examples:
|
||
|
|
|
||
|
|
- ```
|
||
|
|
Example 1:
|
||
|
|
|
||
|
|
Input: nums = [2,3,-2,4]
|
||
|
|
Output: 6
|
||
|
|
Explanation: [2,3] has the largest product 6.
|
||
|
|
|
||
|
|
Example 2:
|
||
|
|
|
||
|
|
Input: nums = [-2,0,-1]
|
||
|
|
Output: 0
|
||
|
|
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
|
||
|
|
|
||
|
|
```
|
||
|
|
|
||
|
|
- Constraints:
|
||
|
|
- `1 <= nums.length <= 2 * 104`
|
||
|
|
- `-10 <= nums[i] <= 10`
|
||
|
|
- The product of any prefix or suffix of `nums` is **guaranteed** to fit in a **32-bit** integer.
|
||
|
|
- Thoughts:
|
||
|
|
- This is a variation of Kadane's algorithm:
|
||
|
|
- We don't change the `localMax` variable based on the value, but we only change it to 1 when it's 0, this is because multiplying a integer always give you a bigger abs. value.
|
||
|
|
- We want to have even number of negative numbers multiplied, when there are odd, one additional negative number must be avoided, to solve this problem, we iterate the array twice, from left to right and from right to left.
|
||
|
|
- Solution:
|
||
|
|
|
||
|
|
- ```java
|
||
|
|
class Solution {
|
||
|
|
public int maxProduct(int[] nums) {
|
||
|
|
// try kadane's algorithm
|
||
|
|
int max = 1;
|
||
|
|
int globalMax = Integer.MIN_VALUE;
|
||
|
|
int globalMax1 = Integer.MIN_VALUE;
|
||
|
|
|
||
|
|
for (int i : nums) {
|
||
|
|
max *= i;
|
||
|
|
globalMax = Math.max(max, globalMax);
|
||
|
|
if (max == 0) {
|
||
|
|
max = 1;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
max = 1;
|
||
|
|
for (int i = nums.length - 1; i >= 0; i--) {
|
||
|
|
max *= nums[i];
|
||
|
|
globalMax1 = Math.max(max, globalMax1);
|
||
|
|
if (max ==0) {
|
||
|
|
max = 1;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return Math.max(globalMax, globalMax1);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
```
|
||
|
|
|
||
|
|
-
|
||
|
|
- TODO:
|
||
|
|
- DONE 写一个 12 bar blues 音乐
|
||
|
|
SCHEDULED: <2023-04-03 Mon>
|