# 221. Maximal Square

`class Solution:    def maximalSquare(self, matrix):        """        :type matrix: List[List[str]]        :rtype: int        """        if not matrix:            return 0        if len(matrix)==0:            return 0        row,col = len(matrix),len(matrix)                def  check(x,y,size):            for i in range(x, x+size):                for j in range(y, y+size):                    if matrix[i][j]=='0':                        return 0            return size**2        maxsize = 0        for i in range(row):            for j in range(col): #start point i,j                if matrix[i][j]=='0':                    continue                for size in range(1, min(row-i,col-j)+1): #decide the size of the window                    maxsize = max(maxsize, check(i,j,size))        return maxsize`
`area = check(i,j,size)if area==0:     breakmaxsize = max(maxsize, check(i,j,size))`
`def  check(x,y,size):            #check the last col            for i in range(x, x+size):                if matrix[i][y+size-1]=='0':                    return 0            #check the last row            for j in range(y, y+size):                if matrix[x+size-1][j]=='0':                    return 0            return size**2` for array sum(j,i)= sum(0,i)-sum(0,j). So that make a sum matrix, from (0,0) to current point sum[i][j]. . the sum from the left up to the bottom right position sum[i][j]-sum[i][y-1]-sum[x-1][j]+sum[x-1][y-1] find the dp function to compute the sums
`def maximalSquare(self, matrix):        """        :type matrix: List[List[str]]        :rtype: int        """        if not matrix:            return 0        if len(matrix)==0:            return 0        row,col = len(matrix),len(matrix)sums = [[0 for _ in range(col+1)] for _ in range(row+1)]        #no need to initialize row 0 and col 0, because we just need it to be 0        for i in range(1, row+1):            for j in range(1, col+1):                sums[i][j]=sums[i-1][j]+sums[i][j-1]-sums[i-1][j-1]+[0,1][matrix[i-1][j-1]=='1']def  check(x,y,size):            count = sums[x+size-1][y+size-1]-sums[x+size-1][y-1]-sums[x-1][y+size-1]+sums[x-1][y-1]            return count if count==size**2 else 0maxsize = 0        for i in range(row):            for j in range(col): #start point i,j                if matrix[i][j]=='0':                    continue                for size in range(1, min(row-i,col-j)+1): #decide the size of the window                    area = check(i+1,j+1,size) #the index in sums need to increase 1                    if area==0:                        break                    maxsize = max(maxsize, area)        return maxsize` use different dp, dp[i][j] means the max size can achieve at (x,y) as bottom right location, if it is 0, then 0, if it is y, min(case1,case2,case3)+1
`def maximalSquare(self, matrix):        """        :type matrix: List[List[str]]        :rtype: int        """        if not matrix:            return 0        if len(matrix)==0:            return 0        row,col = len(matrix),len(matrix)dp = [[0 for _ in range(col+1)] for _ in range(row+1)]        #no need to initialize row 0 and col 0, because we just need it to be 0        maxsize = 0        for i in range(1, row+1):            for j in range(1, col+1):                if matrix[i-1][j-1]=='0':                    dp[i][j]=0                else:                    dp[i][j]=min(dp[i-1][j],dp[i][j-1], dp[i-1][j-1])+1                    maxsize=max(maxsize, dp[i][j])                        return maxsize**2`

# 85. Maximal Rectangle

`def maximalRectangle(self, matrix):        """        :type matrix: List[List[str]]        :rtype: int        """        if not matrix:            return 0        if len(matrix)==0:            return 0        row,col = len(matrix),len(matrix)                def  check(x,y,w,h):            #check the last col            for i in range(x, x+h): #change row                if matrix[i][y+w-1]=='0':                    return 0                           for j in range(y, y+w): #change col                if matrix[x+h-1][j]=='0':                    return 0            return w*h        maxsize = 0        for i in range(row):            for j in range(col): #start point i,j                if matrix[i][j]=='0':                    continue                for h in range(1, row-i+1): #decide the size of the window                    for w in range(1,col-j+1):                        rslt = check(i,j,w,h)                        if rslt==0: #we definitely need to break it. or else we get wrong result                            break                        maxsize = max(maxsize, check(i,j,w,h))        return maxsize`
`def maximalRectangle(self, matrix):        """        :type matrix: List[List[str]]        :rtype: int        """        if not matrix:            return 0        if len(matrix)==0:            return 0        row,col = len(matrix),len(matrix)        sums = [[0 for _ in range(col+1)] for _ in range(row+1)]        #no need to initialize row 0 and col 0, because we just need it to be 0        for i in range(1, row+1):            for j in range(1, col+1):                sums[i][j]=sums[i-1][j]+sums[i][j-1]-sums[i-1][j-1]+[0,1][matrix[i-1][j-1]=='1']                def  check(x,y,w,h):            count = sums[x+h-1][y+w-1]-sums[x+h-1][y-1]-sums[x-1][y+w-1]+sums[x-1][y-1]            return count if count==w*h else 0maxsize = 0        for i in range(row):            for j in range(col): #start point i,j                if matrix[i][j]=='0':                    continue                for h in range(1, row-i+1): #decide the size of the window                    for w in range(1,col-j+1):                        rslt = check(i+1,j+1,w,h)                        if rslt==0: #we definitely need to break it. or else we get wrong result                            break                        maxsize = max(maxsize, rslt)        return maxsize`
`def maximalRectangle(self, matrix):        """        :type matrix: List[List[str]]        :rtype: int        """        if not matrix:            return 0        if len(matrix)==0:            return 0        def getMaxAreaHist(heights):            if not heights:                return 0            maxsize = max(heights)stack = [-1]#the stack will only grow            for i, h in enumerate(heights):                if stack[-1]!=-1:                    if h>heights[stack[-1]]:                        stack.append(i)                    else:                        #start to kick to pop and compute the area                        while stack[-1]!=-1 and h<=heights[stack[-1]]: #same or equal needs to be pop out                            idx = stack.pop()                            v = heights[idx]                            maxsize=max(maxsize, (i-stack[-1]-1)*v)                        stack.append(i)else:                    stack.append(i)            #handle the left stack            while stack[-1]!=-1:                idx = stack.pop()                v = heights[idx]                maxsize=max(maxsize, (len(heights)-stack[-1]-1)*v)            return maxsize        row,col = len(matrix),len(matrix)        heights =*col #save the maximum heights till here        maxsize = 0        for r in range(row):            for c in range(col):                if matrix[r][c]=='1':                    heights[c]+=1                else:                    heights[c]=0            #print(heights)            maxsize = max(maxsize, getMaxAreaHist(heights))        return maxsize`

# 84. Largest Rectangle in Histogram

`class Solution:    def largestRectangleArea(self, heights):        """        :type heights: List[int]        :rtype: int        """        if not heights:            return 0        maxsize = max(heights)                for i in range(len(heights)):            minheight = heights[i]            width = 1            for j in range(i+1, len(heights)):                width+=1                minheight = min(minheight, heights[j])                maxsize = max(maxsize,minheight*width)        return maxsize`
`def largestRectangleArea(self, heights):        """        :type heights: List[int]        :rtype: int        """        if not heights:            return 0        maxsize = max(heights)                stack = [-1]                #the stack will only grow        for i, h in enumerate(heights):            if stack[-1]!=-1:                if h>heights[stack[-1]]:                    stack.append(i)                else:                    #start to kick to pop and compute the area                    while stack[-1]!=-1 and h<=heights[stack[-1]]: #same or equal needs to be pop out                        idx = stack.pop()                        v = heights[idx]                        maxsize=max(maxsize, (i-stack[-1]-1)*v)                    stack.append(i)                            else:                stack.append(i)        #handle the left stack        while stack[-1]!=-1:            idx = stack.pop()            v = heights[idx]            maxsize=max(maxsize, (len(heights)-stack[-1]-1)*v)        return maxsize`

# 188. Best Time to Buy and Sell Stock IV

`def maxProfit(self, k, prices):        """        :type k: int        :type prices: List[int]        :rtype: int        """        if not prices or len(prices)==1:            return 0        #we track the peak or bottom of the line        i,j = 0,1        diffs = []        while j<len(prices):            if prices[j]>=prices[j-1]:                j+=1            else:                #record the last peak                diffs.append(prices[j-1]-prices[i])                i=j                j=j+1        diffs.append(prices[-1]-prices[i])        diffs.sort(reverse=True)        print(diffs)        return sum(diffs[:k]) if k<=len(diffs) else sum(diffs)`

--

--