输入一个长度为n的整形数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的乘积的最大值。Java代码实现
时间: 2024-12-19 07:28:57 浏览: 6
这个问题可以通过动态规划来解决。我们可以维护两个变量:`maxProduct` 和 `currentMax`。`maxProduct` 存储的是当前找到的最大子数组乘积,而 `currentMax` 则存储当前连续正数的最大乘积,一旦遇到负数,就需要更新 `currentMax` 为 1,因为负数乘以负数仍然是正数,我们希望能尽可能地延长连续的正数序列。
以下是Java代码实现:
```java
import java.util.Stack;
public class MaxSubArrayProduct {
public static int getMaxSubarrayProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int maxProduct = nums[0];
int currentMax = nums[0];
boolean isNegative = false; // 标记是否遇到过负数
Stack<Integer> negations = new Stack<>(); // 负数标记栈
for (int num : nums) {
if (num < 0) {
if (!isNegative) {
// 当前遇到第一个负数,记录当前位置并清空连续正数序列
isNegative = true;
negations.push(-1);
} else {
// 后续的负数,更新currentMax为1
currentMax = 1;
negations.push(-1);
}
} else {
// 遇到正数,如果栈顶元素也是正数,则合并;否则结束连续正数序列,计算乘积
if (negations.peek() > 0) {
currentMax *= negations.pop();
}
currentMax *= num;
// 如果栈为空或栈顶元素是负数,更新maxProduct
if (negations.isEmpty() || negations.peek() < 0) {
maxProduct = Math.max(maxProduct, currentMax);
}
}
}
return maxProduct;
}
public static void main(String[] args) {
int[] nums = {1, -2, 3, 4};
System.out.println(getMaxSubarrayProduct(nums)); // 输出12
}
}
```
在这个代码中,我们会遍历整个数组,遇到负数时处理连续负数序列,遇到正数时结合之前的正数或单独的正数计算当前子数组的最大乘积。
阅读全文