<p>Given an array of integers <code>nums</code>, find the maximum length of a subarray where the product of all its elements is positive.</p>

<p>A subarray of an array is a consecutive sequence of zero or more values taken out of that array.</p>

<p>Return <em>the maximum length of a subarray with positive product</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,-2,-3,4]
<strong>Output:</strong> 4
<strong>Explanation:</strong> The array nums already has a positive product of 24.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [0,1,-2,-3,-4]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The longest subarray with positive product is [1,-2,-3] which has a product of 6.
Notice that we cannot include 0 in the subarray since that&#39;ll make the product 0 which is not positive.</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [-1,-2,-3,0,1]
<strong>Output:</strong> 2
<strong>Explanation:</strong> The longest subarray with positive product is [-1,-2] or [-2,-3].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

'''
題目是要找出list中
最長連續範圍中的數字相乘出來的結果可以是正的
但有個洞就是0不能包含在裡面
因為0是沒有正負的

一開始的想法是
如果當下遇到一個負數，使得整體結果變成負的
那就要期望，接下來可以再遇到一個負數
如果接下來一直遇不到負數，就表示除了這個位置
接下來其他的位置都是正數
那就看這些位置的長度是多少

所以如果題目是這樣
012345  
++-+++

走到第二格時，因為遇到負數了，所以先記錄當下最長是2
然後如果這個負數如果是之後可以被抵銷的話，那到他這格式3，所以可以另外記錄一個3 
表示如果之後有遇到負的，就可以加3回來
然後走第3格時，先從1重新開始算

一開始是先寫了這樣
class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        result = 0
        curLen = 0
        curNegLen = 0

        for i in range(len(nums)):
            if nums[i] > 0:
                curLen += 1
            elif nums[i] < 0:
                if curNegLen != 0:
                    curLen += curNegLen + 1
                    curNegLen = 0
                else:
                    curNegLen = curLen + 1
                    curLen = 0
            elif nums[i] == 0:
                curLen = 0
                curNegLen = 0

            result = max(result, curLen)
        return result

但是會死在這個測資
[5,-20,-20,-39,-5,0,0,0,36,-32,0,-7,-10,-7,21,20,-12,-34,26,2]
正確答案要為8
但是我的輸出是6
問題是出在後面這段
經過了0歸零之後
從以下開始
-7,-10,-7,21,20,-12,-34,26,2
照上面的寫法
計算會停在-7~-12 =>六個
算到-34之後就會因為變負數，而且後面沒有其他的負數，所以最終就錯了
因為可以不看第0個-7，而從-10來看
答案就會是正確的8
==============================
後來重想一下
如果是最好的情況
1.全部都是正的
2.全部的element中，有負數的element是雙數
所以如果可以先掃一次
知道了全部負數的位置跟數量

如果是雙數，那就沒問題，就是最好的情況
如果是單數，就是看左右兩側要先拿掉哪一邊
假如
最開頭~第一個負數
跟
最尾巴~倒數第一個負數
看哪一個中間這段可以損失的少
(也就是該位置是離開頭 或尾巴比較近的)
就以他改為起點(或終點)，這樣就可以保有最長的整段

那如果第一個負數點跟最後一個負數點，距離頭尾很遠
那就表示反而
頭~第一個點
或
尾~倒數第一個點是比較長的

以上想到最後又亂掉
============================
再一次重想

先用一個指標從頭開始走
如果有遇到負數
表示現在是遇到單數個負數
所以
--------------O|
之前到負數前一格
這段距離是合法的

然後再繼續往下走
如果又遇到一個負數
那表示現在有雙數個負數
所以就是這整段都是合法的
-------------|-----|

note:
雖然兩個負數之間，也是合法的
但是再怎麼樣不可能比從頭開始算還要來的長

如果有遇到第三個負數，為單數
那就是在第三個負數之前，都是合法的
-------------|-----|---------O|

再這樣以此類推下去
等到走到底之後
如果此時的負數個數是雙數，那就沒有問題，整段都是合法的
但如果負數個數是單數
那就不看第一個負數(整體就只會剩下雙數個負數)
-------------|0----|----------|
從第一個負數後面一格到最後的距離
有沒有比之前所記到的結果還要多，來決定最後的結果

那因為還有一個0的規則
所以只要遇到0，就代表一段的結束
再往後走就是都再重新開始算

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        ptr = 0
        isPair = True
        result = 0
        curResult = 0
        firstNegPos = -1
        startPos = 0
        while ptr < len(nums):
            if nums[ptr] > 0:
                if isPair:
                    curResult = ptr - startPos +1
            elif nums[ptr] < 0:
                if firstNegPos == -1:
                    firstNegPos = ptr
                if isPair:
                    isPair = False
                else:
                    isPair = True
                    curResult = ptr - startPos +1
            elif nums[ptr] == 0: #遇到0同等於一個小結束
                if not isPair: #每一段結束，如果這段的負數不是雙數，那就把最一開始的負數忽略，看從它的下一個~最後一個的長度
                    result = max(result, (ptr-1) - (firstNegPos+1)+1) 
                isPair = True
                curResult = 0
                startPos = ptr+1
                firstNegPos = -1

            result = max(result, curResult)
            if startPos >= len(nums):
                break
            ptr += 1

        if not isPair:#最後一段結束，一樣做一次每次結束都要做的
            result = max(result, (ptr-1) - (firstNegPos+1)+1)
        return result
=================
後來偷看討論區解答，看到這個很dynamic的greedy
太神奇了捷克
不過如果比起來，我上面的解法，是比較省空間
而且速度上來說，也都是O(N)
(只差在我每次遇到0，或結束時，需要檢查是不是雙數的負數，然後不是的話要去掉頭，這樣速度也沒太多影響)
'''
class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        n = len(nums)
        pos, neg = [0] * n, [0] * n
        if nums[0] > 0: pos[0] = 1
        if nums[0] < 0: neg[0] = 1
        ans = pos[0]
        for i in range(1, n):
            if nums[i] > 0:
                pos[i] = 1 + pos[i - 1]
                neg[i] = 1 + neg[i - 1] if neg[i - 1] > 0 else 0
            elif nums[i] < 0:
                pos[i] = 1 + neg[i - 1] if neg[i - 1] > 0 else 0
                neg[i] = 1 + pos[i - 1]
            ans = max(ans, pos[i])
        print(pos)
        print(neg)
        return ans
31700