<p>Given a <code>rows x cols</code>&nbsp;binary <code>matrix</code> filled with <code>0</code>&#39;s and <code>1</code>&#39;s, find the largest rectangle containing only <code>1</code>&#39;s and return <em>its area</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/14/maximal.jpg" style="width: 402px; height: 322px;" />
<pre>
<strong>Input:</strong> matrix = [[&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;],[&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;]]
<strong>Output:</strong> 6
<strong>Explanation:</strong> The maximal rectangle is shown in the above picture.
</pre>

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

<pre>
<strong>Input:</strong> matrix = [[&quot;0&quot;]]
<strong>Output:</strong> 0
</pre>

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

<pre>
<strong>Input:</strong> matrix = [[&quot;1&quot;]]
<strong>Output:</strong> 1
</pre>

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

<ul>
	<li><code>rows == matrix.length</code></li>
	<li><code>cols == matrix[i].length</code></li>
	<li><code>1 &lt;= row, cols &lt;= 200</code></li>
	<li><code>matrix[i][j]</code> is <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        #start  end     act1                act2
        #0      0       commit              drop
        #0      2       cut_commit_keep     add_rmndr
        #0             
        #
        #

        #rect : [ s,e,cnt, [c1,c2...] ] #childs are disjoint!; anyway optimal rectangles are ither non adjecent 
        #one one includes other



        def get_spans(row):
            res=[]
            start=None
            for i,v in enumerate(row):
                if start is None:
                    if v=='1':
                        start=i
                else:
                    if v=='0':
                        res.append( [start,i,1,[]]  ) 
                        start=None       

            if start is not None:
                res.append( [start,i+1,1,[]]  )            
            return res    

        def area(rect,add):
            return (rect[1]-rect[0])*(rect[2]+add)

        def commit(rect,best,add=0):
            return max( best, area(rect,add), *( commit(rect_cld,0,add+rect[2]) for rect_cld in rect[3] )   )

        def cut_commit_keep(rect,best,loc,add=0):
            new_rect=[ loc,rect[1], rect[2], []   ]

            best=max(best, area(rect,add)   )
            for cld in rect[3]:
                if cld[1]<=loc:
                    best=commit(cld,best,rect[2]+add)
                elif cld[0]<loc:
                    best,cut_cld = cut_commit_keep( cld, best, loc,rect[2]+add )
                    new_rect[3].append(cut_cld)
                else:
                    new_rect[3].append( cld  )

            return best, new_rect     

        def cut_keep_commit(rect,best,loc,add=0):
            new_rect=[rect[0],loc, rect[2], []] 
            best=max(best, area(rect,add)   )    
            for cld in rect[3]:
                if cld[0]>=loc:
                    best=commit(cld,best,rect[2]+add)
                elif cld[1]>loc:
                    best,cut_cld = cut_keep_commit(cld,best,loc,rect[2]+add)   
                    new_rect[3].append(cut_cld)
                else:
                    new_rect[3].append(cld)
            return best,new_rect        

        def cut_keep_keep(rect,best,loc,add=0):
            l_rect=[ rect[0], loc, rect[2], []  ]
            r_rect=[ loc,rect[1], rect[2],[]  ]
            best=max(best,area(rect,add))
            for cld in rect[3]:
                if cld[1]<=loc:
                    l_rect[3].append(cld)
                elif cld[0]>=loc:
                    r_rect[3].append(cld)
                else:
                    best, l_cld, r_cld = cut_keep_keep( cld, best,loc, rect[2]+add   )        
                    l_rect[3].append(l_cld)
                    r_rect[3].append(r_cld)

            return best, l_rect, r_rect        


        def get_next(i,lst):
            if len(lst)>i:
                return i+1, lst[i]
            else:
                return i, None    

        L=len(matrix)
        best=0
        struct=[]
        for row in matrix:
            struct_new=[]

            j,prev=get_next(0,struct)
            spans=get_spans(row)
            k,span=get_next(0,spans)

            #print(prev,span)
            while prev is not None or span is not None:
                if prev is None:
                    struct_new.append(span)
                    k,span=get_next(k,spans)

                elif span is None:    
                    best=commit( prev, best  )
                    j,prev=get_next(j,struct)

                else:    
                    e1=prev[1]
                    e2=span[1]
                    #decide on left part
                    if prev[1]<=span[0]:
                        best=commit(prev,best)
                        prev=None
                    elif prev[0]<span[0]:
                        best,prev=cut_commit_keep( prev, best, span[0]  )    
                    else:
                        pass

                    #decide on combination
                    prev_next=None
                    if prev is not None:
                        if prev[0]>=span[1]:
                            prev_next=prev #no combination
                            prev=None
                        elif prev[1]>span[1]: #slicing
                            if len(spans)>k and prev[1]>spans[k][0]:
                                best,prev,prev_next=cut_keep_keep( prev,best, span[1]  )
                            else:
                                best,prev=cut_keep_commit(prev,best,span[1])    
                        else:
                            pass

                    if prev is not None:
                        if prev[0]==span[0] and prev[1]==span[1]:
                            span=prev
                            span[2]+=1
                        else:
                            span[3].append(prev)   

                    #decide on next prev
                    if prev_next is not None:
                        prev=prev_next
                    else:
                        j,prev=get_next(j,struct)            

                    #on next span
                    if e1>=e2:
                        if not span[3] and ( span[2]+L-k  )*(span[1]-span[0]  ) <=best:
                            pass
                        else:    
                            struct_new.append(span)
                        k,span=get_next(k,spans)    
            struct=struct_new
            #print(struct,best)
        for prev in struct:
            best=commit(prev,best)
 
        return best
                
18400