如何将数组中m个连续整数最大乘积解法优化至O(N)时间复杂度？

首先说下你原代码里的几个明显问题：

• 参数类型用错了，Array[]是反射包下的类，实际应该用int[]来表示整数数组
• Arrays.asList(a).indexOf(j)是逻辑错误，这是找数值j在数组里的索引，不是取数组第j位置的元素，正确写法是直接取a[j]
• 原代码时间复杂度是O(N*m)，每个窗口都要循环m次计算乘积，这正是需要优化的点

要把时间复杂度降到O(N)，我们可以用滑动窗口结合维护当前窗口最大/最小乘积的方式（数组里可能有负数，负负得正的情况会让最小乘积变成最大的，所以必须同时跟踪这两个值）。具体实现思路：

1. 处理边界情况：如果数组长度小于m，直接返回0
2. 初始化前m个元素的乘积，同时记录这段的最大和最小乘积
3. 从第m个元素开始遍历，每次滑动窗口时：
   • 计算三个候选值：当前元素本身、当前元素乘前窗口的最大乘积、当前元素乘前窗口的最小乘积
   • 用这三个值更新当前窗口的最大和最小乘积
   • 同步更新全局的最大乘积
4. 最后返回全局最大乘积

修正后的Java代码如下：

import java.util.*;

public class Part1 {
    public static int maxProduct(int[] a, int m) {
        int n = a.length;
        if (n < m) {
            return 0;
        }

        int globalMax = Integer.MIN_VALUE;
        int currentMax = 1;
        int currentMin = 1;

        // 初始化第一个窗口的乘积与当前最大/最小乘积
        for (int i = 0; i < m; i++) {
            currentMax *= a[i];
            currentMin *= a[i];
        }
        globalMax = currentMax;

        // 滑动窗口处理后续元素
        for (int i = m; i < n; i++) {
            int prevMax = currentMax;
            // 基于前窗口的最值计算当前窗口的新最值
            currentMax = Math.max(a[i], Math.max(prevMax * a[i], currentMin * a[i]));
            currentMin = Math.min(a[i], Math.min(prevMax * a[i], currentMin * a[i]));
            // 更新全局最大乘积
            globalMax = Math.max(globalMax, currentMax);
        }

        return globalMax;
    }

    // 测试用例
    public static void main(String[] args) {
        int[] testArray = {2, 3, -2, 4};
        System.out.println(maxProduct(testArray, 2)); // 预期输出6
    }
}

补充说明：

• 维护currentMin是因为当窗口存在负数时，新加入的负数元素会让原本的最小乘积（负数）变成正数，可能成为新的最大乘积，不跟踪的话会漏掉这种情况
• 这个方案只需要遍历数组两次（初始化窗口+滑动窗口），时间复杂度为O(N)，完全符合要求

内容的提问来源于stack exchange，提问作者Jerome