题解 | #乘积为正数的最长连续子数组#
乘积为正数的最长连续子数组
https://www.nowcoder.com/practice/0112b9b5a09048d89309f55ea666db91
思路：
首先乘积为正数，只取决于因数的正负和是否为0，所以所有数只需分为正数、负数和0三种而不用关心具体数值。
然后是递推过程，需要用两个变量dpmaxn和dpfmaxn记录以当前数结尾的乘积为正/负数的连续子数组最长长度，然后用一个变量maxn记录最大的dpmaxn值,最后这个maxn就是我们要求得的结果。
时间复杂度：O(n)
空间复杂度：O(1)
代码如下，目前用时和内存占用都是最少的
#include<cstdio>
using namespace std;
template <typename T>
inline void read(T& f) {
f = 0;
T fu = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') {
fu = -1;
}
c = getchar();
}
while (c >= '0' && c <= '9') {
f = (f << 3) + (f << 1) + (c & 15);
c = getchar();
}
f *= fu;
}
template <typename T>
inline void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x < 10) putchar(x + 48);
else print(x / 10), putchar(x % 10 + 48);
}
int main(){
int dpmaxn = 0, dpfmaxn = 0; //以i结尾的正/负数的子数组最长长度
int tmaxn, tfmaxn;
int n, num, maxn = 0;
read(n);
while(n--){
read(num);
if(num > 0){
tmaxn = dpmaxn + 1;
tfmaxn = dpfmaxn == 0 ? 0 : dpfmaxn + 1;
}
else if(num < 0){
tmaxn = dpfmaxn == 0 ? 0 : dpfmaxn + 1;
tfmaxn = dpmaxn == 0 ? 1 : dpmaxn + 1;
}
else{
tmaxn = tfmaxn = 0;
}
dpmaxn = tmaxn, dpfmaxn = tfmaxn;
if(dpmaxn > maxn)maxn = dpmaxn;
}
print(maxn);
return 0;
}
查看13道真题和解析
