C++ | Easy Undertsand | No DP |1 Pass |O(n) |Counting Negative Numbers in subarray | linear Solution
What is the case for subarray product to be positive?\n1.Subarray should not contain 0\n2.Subarray should contain either no negative elements or even number of 
What is the case for subarray product to be positive?\n*1.Subarray should not contain 0\n2.Subarray should contain either no negative elements or even number of negative elements*\n\narr = {1,-1,1,1,-1,1,-1,1,1}\nstart = 0\nend = 8\nfirstIndexHavingNegativeValue = 1\nlastIndexHavingNegativeValue = 6\n\nThis subarray contains odd number of negative elements so what will be the answer?\n1. If negative elements is even then return end - start +1 -> whole subarray\n2. If negative elements are odd the return maximum of these 2\n\t1. (end - firstIndexHavingNegativeValue)  i.e. 1,1,-1,1,-1,1,1 -> 7\n\t2. (lastIndexHavingNegativeValue - start) i.e. 1,1,-1,1,-1,1,1 -> 6\n\t\n\n\nAlgorithm-\n1. int start = 0;\n    int end = 0;\n    int firstNegativeIndex = -1;\n    int lastNegativeIndex = -1;\n    int negCount = 0;\n    int ans = 0;\n2. if number if positive then continue\n3. If the number is negative\n\t1.Increase NegativeNumberCount by 1 \n\t2. Update the firstNegativeIndex and lastNegativeIndex\n4. If number is 0 then we need to get the answer from start, i-1 and update the answer(searching in subarray which is behind 0, because from 0 we will have a next subarray as we are not going to include 0 in our subarray product)\n5. After the end of the array again check the answer in start to n-1 and update with max\n\n\n\n```\nclass Solution {\npublic:\n    \n    int getAns(int start, int end, int fi, int li, int negCount ){\n        if(start > end){\n            return 0;\n        }\n        if(negCount %2 == 0){\n            return (end-start + 1);\n        }\n        return max( (end-fi), (li-start)) ; \n    }\n    \n    \n    int getMaxLen(vector<int>& nums) {\n        // finding longest subarray with even number of negative numbers and should not contain 0\n        int n = nums.size();\n        int start = 0;\n        int end = 0;\n        int firstNegativeIndex = -1;\n        int lastNegativeIndex = -1;\n        int negCount = 0;\n        int ans = 0;\n        \n        for(int i = 0 ; i < n ; i++){\n            if(nums[i] > 0){\n                \n            }\n            else if(nums[i] < 0){\n                negCount += 1;\n                if(firstNegativeIndex == -1){\n                    firstNegativeIndex = i;\n                }\n                lastNegativeIndex = i;\n            }\n            else{\n                end = i - 1;\n                ans = max(ans, getAns(start,end, firstNegativeIndex, lastNegativeIndex, negCount ));\n                start = i+1;\n                end = i+1;\n                firstNegativeIndex = -1;\n                lastNegativeIndex = -1;\n                negCount = 0;\n            }\n        }\n        if(start < n){\n            ans = max(ans, getAns(start, n-1 ,firstNegativeIndex, lastNegativeIndex, negCount ));\n        }\n        \n        return ans;\n        \n    }\n};\n```\n\n\nTime Complexity - O(N)\nSpace Complexity - O(1)\n
['C', 'C++']