本文主要是介绍牛客网 DP8.乘积为正数的最长连续子数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题也是关于DP的问题。
思路：我们在求最大连续子数组乘积的题当中知道，我们在求乘法的最大乘积的时候需要考虑两个情况，一种就是正数，一种就是负数，相对应的，极端来说就是最大值和最小值。这里也有相似的思想之处，也请读者联系一下之前的那道题。
这里并没有要求我们求最大的数，是求最大的长度。先抛开长度不管，我们需要先研究怎么样才能乘积最大，你可能会说直接用之前最大连续子数组的乘积就行了嘛。不是的，上一次那道题我们只需要知道结果就可以了，过程什么的我们不关心，但是这里既然说是长度了，那就一定涉及到一定的过程原理。所以我们不能完全照搬那里的思路了。
这里我们也需要考虑数的情况，分三种，正数，负数，0。负负得正让我们知道，有必要保留上一步负数的乘积。所以我们需要准备两个数组，一种就是处理正数的dp，表示连续相乘是正数的数组长度，一种就是处理负数的dp，表示连续相乘是负数的长度。
当我们开始读取数的时候，需要判断它的正负。如果是正数，我们就直接放到正数的dp当中进行筛选；当然，如果说这个时候负数的dp中存在数的话，我们也需要考虑加入负数的dp当中。因为负数里面，乘以正数后也一定是负数。考虑到最小值也可能因为乘以负数变成最大值（前提是最小值是负数，但当然会是负数，所以要留心），我们也要考虑这种情况所以才会加入这个数到负数dp中的。
同理，我们读取负数的时候，需要考虑，当这个数乘以正数的dp时，是不是就会变成负数了？所以这个时候会加入到复数的dp个数当中而不是正数的dp当中，切记！同理，当负数这里的dp不为空的时候，我们需要知道，此时负数乘以负数就会加入到正数的dp当中了。
为0的时候很好处理，乘积就直接变为0了。
上代码：
#include <iostream>
#define MAX 100010
using namespace std;
typedef long long LL;
LL dp1[MAX];
LL dp2[MAX];
int main() {int n;cin>>n;LL a;LL res=-9999999;for(int i=0;i<n;i++){cin>>a;if(a==0)dp1[i]=dp2[i]=0;else if(a>0){dp1[i]=max(dp1[i-1]+1,dp1[i]);if(dp2[i-1])dp2[i]=max(dp2[i-1]+1,dp2[i]);}else{dp2[i]=max(dp1[i-1]+1,dp2[i]);if(dp2[i-1])dp1[i]=max(dp2[i-1]+1,dp1[i]);}res=max(res,dp1[i]);}cout<<res;
}这篇关于牛客网 DP8.乘积为正数的最长连续子数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
