C++| O(n) | DP | With Explanation
Approach #\nI would suggest to first solve https://leetcode.com/problems/maximum-product-subarray/.\nThis solution is based on the concepts of this previous, mo
# Approach #\nI would suggest to first solve https://leetcode.com/problems/maximum-product-subarray/.\nThis solution is based on the concepts of this previous, more trivial/standard question.\nAnyways, I wil explain assuming you haven\'t solved it :)\n\nThis question enquires about the longest positive value product. Let\'s first assume that input array consists of only non-negative numbers. This question has a trivial solution, we can traverse the array in linear time while maintaining a counter for the current longest chain of positive numbers. If we get a zero value in the array, We reset the counter to zero. \nThe maximum value of this counter at any point of time during this operation will be the answer.\n\nNow comes the tricky part, what if there are negative numbers?\nIn this case, we will need to maintain two counters, one for the current longest chain of positive numbers and another for the current longest chain of negative numbers. \nWhile traversing the array, \n*  If we get a positive number, Increment the counters by one. \n* If we get a negative number, Exchange the longest positive and negative chain\'s counter\'s values. \n* If we get zero, Reset both counters to zero.\n\nThere is a small flaw with this though, what if we get the following array, A = [1,2,3,4,-5]. We should not increment the negative chain\'s counter value here until index 4, as the product will always remain positive. Conversely, we get A = [-1, 2, 3]. We should not increment the positive counter at index 0. \n\nTo tackle this problem, Upon getting a positive number in the array increment the negative counter only if the size of negative chain was already non-zero. Conversely, do the same for the positive counter.\n\n# Solution #\n```\nclass Solution {\npublic:\n    int getMaxLen(vector<int>& nums) {\n        int pos = 0, neg=0, temp, ans=0;\n        for(int i=0;i<nums.size();i++){\n            if(nums[i] == 0){\n                pos = 0;\n                neg = 0;\n            }\n            else if(nums[i] > 0){\n                pos++;\n                if(neg>0)\n                    neg++;\n            }\n            else{\n                if(neg>0)\n                    temp = neg + 1;\n                else\n                    temp = 0;\n                neg = pos+1;\n                pos = temp;\n            }\n            ans = max(ans, pos);\n        }\n        return ans;\n    }\n};\n```\n# Complexity #\nTime complexity - O(n)\nSpace complexity - O(1)
['Dynamic Programming', 'C']