求助一道array的题，lc没找到一样的

Given an array of numbers of size N (a large number, say N=1000000), find out the largest product of n-number of adjacent numbers (n<N, say n=4).For example, if the array is
Int[] nums = {2,1,3,4,-9,6, 0, -34, 0, -456, 9,0, 23,275, 0, 302, -42, -63,7564,……};
if n =4, calculate products of adjacent elements like this
P1= 2x1x3x4,
P2 = 1x3x4x(-9),
P3 = 3x4x9x6,
etc.…..
And find out the largest of the product P1,P2, P3,… for this array.
Please write a function with array and n as input, return the largest product.

请问除了brute force的O(n * N)，应该如何optimize？主要是数组里既有正负数也有0，一下子想不出来好的解法。

直接sliding window? 遇到0把left重置到下一个非0的数字，然后right从left重新开始移，时间O(n)空间O(1)

楼主看一下蠡口152, 比起来是没有长度限制, 相对来说更难一点, 基本是用DP解, 不过固定长度的话 sliding window肯定可以做的.

Actuant 发表于 2020-3-10 01:55
直接sliding window? 遇到0把left重置到下一个非0的数字，然后right从left重新开始移，时间O(n)空间O(1)

+1
也可以在记录滑动乘积的同时记录滑动非零乘积和窗口内0的数量，复杂度也是O(n)