Leetcode: Sword finger offer 63 Maximum profit of stock [record prefix minimum and or no brain segment tree]

analysis

No brain segment tree records the following maximum value
Then prefix the minimum and record the previous minimum

Anencephalic segment tree

from functools import reduce

class SegTree:
    '''  General segment tree  by AK automata   Support incremental updates , Covering the update , Sequence update , arbitrarily RMQ operation   Based on binary tree implementation   initialization ：O(1)  The single operation complexity of incremental update or overwrite update ：O(log k)  Single time complexity of sequence update ：O(n) https://github.com/boristown/leetcode/blob/main/SegTree.py '''
    def __init__(self, f1, f2, l, r, v = 0):
        '''  Initializing line segment tree [left,right) f1,f2 Example ：  Line segments and : f1=lambda a,b:a+b f2=lambda a,n:a*n  Segment maximum : f1=lambda a,b:max(a,b) f2=lambda a,n:a  The minimum value of the line segment : f1=lambda a,b:min(a,b) f2=lambda a,n:a '''
        self.ans = f2(v,r-l)
        self.f1 = f1
        self.f2 = f2
        self.l = l #left
        self.r = r #right
        self.v = v #init value
        self.lazy_tag = 0 #Lazy tag
        self.left = None #SubTree(left,bottom)
        self.right = None #SubTree(right,bottom)
    
    @property
    def mid_h(self):
        return (self.l + self.r) // 2

    def create_subtrees(self):
        midh = self.mid_h
        if not self.left and midh > self.l:
            self.left = SegTree(self.f1, self.f2, self.l, midh)
        if not self.right:
            self.right = SegTree(self.f1, self.f2, midh, self.r)

    def init_seg(self, M):
        '''  Initializes the value of the segment tree to a matrix Matrx  Input guarantee Matrx Consistent with the line segment size  '''
        m0 = M[0]
        self.lazy_tag = 0
        for a in M:
            if a!=m0:
                break
        else:
            self.v = m0
            self.ans = self.f2(m0,len(M))
            return self.ans
        self.v = '#'
        midh = self.mid_h
        self.create_subtrees()
        self.ans = self.f1(self.left.init_seg(M[:midh-self.l]), self.right.init_seg(M[midh-self.l:]))
        return self.ans
    
    def cover_seg(self, l, r, v):
        '''  Put the line segment [left,right) Overlay as val '''
        if self.v == v or l >= self.r or r <= self.l:
            return self.ans
        if l <= self.l and r >= self.r:
            self.v = v
            self.lazy_tag = 0
            self.ans = self.f2(v,self.r-self.l)
            return self.ans
        self.create_subtrees()
        if self.v != '#':
            if self.left:
                self.left.v = self.v
                self.left.ans = self.f2(self.v,self.left.r-self.left.l)
            if self.right:
                self.right.v = self.v
                self.right.ans = self.f2(self.v,self.right.r-self.right.l)
            self.v = '#'
        #push up
        self.ans = self.f1(self.left.cover_seg(l, r, v),self.right.cover_seg(l, r, v))
        return self.ans

    def inc_seg(self, l, r, v):
        '''  Put the line segment [left,right) increase val '''
        if v == 0 or l >= self.r or r <= self.l:
            return self.ans
        #self.ans = '?'
        if l <= self.l and r >= self.r:
            if self.v == '#':
                self.lazy_tag += v
            else:
                self.v += v
            self.ans += self.f2(v,self.r-self.l)
            return self.ans
        self.create_subtrees()
        if self.v != '#':
            self.left.v = self.v
            self.left.ans = self.f2(self.v,self.left.r-self.left.l)
            self.right.v = self.v
            self.right.ans = self.f2(self.v,self.right.r-self.right.l)
            self.v = '#'
        self.pushdown()
        self.ans = self.f1(self.left.inc_seg(l, r, v),self.right.inc_seg(l, r, v))
        return self.ans

    def inc_idx(self, idx, v):
        ''' increase idx by val '''
        if v == 0 or idx >= self.r or idx < self.l:
            return self.ans
        if idx == self.l == self.r - 1:
            self.v += v
            self.ans += self.f2(v,1)
            return self.ans
        self.create_subtrees()
        if self.v != '#':
            self.left.v = self.v
            self.left.ans = self.f2(self.v,self.left.r-self.left.l)
            self.right.v = self.v
            self.right.ans = self.f2(self.v,self.right.r-self.right.l)
            self.v = '#'
        self.pushdown()
        self.ans = self.f1(self.left.inc_idx(idx, v),self.right.inc_idx(idx, v))
        return self.ans

    def pushdown(self):
        if self.lazy_tag != 0:
            if self.left:
                if self.left.v != '#':
                    self.left.v += self.lazy_tag
                    self.left.lazy_tag = 0
                else:
                    self.left.lazy_tag += self.lazy_tag
                self.left.ans += self.f2(self.lazy_tag, self.left.r-self.left.l)
            if self.right:
                if self.right.v != '#':
                    self.right.v += self.lazy_tag
                    self.right.lazy_tag = 0
                else:
                    self.right.lazy_tag += self.lazy_tag
                self.right.ans += self.f2(self.lazy_tag, self.right.r-self.right.l)
            self.lazy_tag = 0

    def query(self, l, r):
        '''  Query line segment [right,bottom) Of RMQ '''
        if l>=r: return 0
        if l <= self.l and r >= self.r:
            return self.ans
        if self.v != '#':
            return self.f2(self.v, min(self.r, r) - max(self.l, l))
        midh = self.mid_h
        anss = []
        if l < midh:
            anss.append(self.left.query(l, r))
        if r > midh:
            anss.append(self.right.query(l, r))
        return reduce(self.f1,anss)


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        # Segment maximum :
        f1=lambda a,b:max(a,b)
        f2=lambda a,n:a
        seg = SegTree(f1,f2,0,n,0)

        for i, price in enumerate(prices):
            seg.inc_idx(i, price)


        ans = 0
        for i, price in enumerate(prices):
            buy = price
            sell = seg.query(i,n)
            if sell > buy:
                ans = max(ans, sell - buy)
        
        return ans

Brain prefix minimum

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #  Record prefix minimum 
        n = len(prices)
        if n <= 1:
            return 0
        preMin = [inf] * n
        preMin[0] = prices[0]
        for i in range(1, n):
            preMin[i] = min(preMin[i - 1], prices[i])
        
        ans = 0
        for i in range(n):
            ans = max(ans, prices[i] - preMin[i])
        
        return ans

summary

Prefix minimum