# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
global maxpathsum
maxpathsum = (1<<31)
def getmaxsum(node):
if not node:
return 0
global maxpathsum
maxsum = node.val
leftmax = getmaxsum(node.left)
rightmax = getmaxsum(node.right)
if leftmax > 0:
maxsum += leftmax
if rightmax > 0:
maxsum += rightmax
maxpathsum = max(maxpathsum, maxsum)
return max(node.val, node.val + leftmax, node.val + rightmax)
getmaxsum(root)
return maxpathsum
bboczeng
@bboczeng
Posts made by bboczeng

114ms Python AC code with a global variable

Heapq for python AC code.
# Definition for singlylinked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ if not lists: return [] heap = [] firstlists = [] for i in range(len(lists)): firstlists.append(lists[i]) for i in range(len(firstlists)): if firstlists[i]: val = firstlists[i].val firstlists[i] = firstlists[i].next heapq.heappush(heap, (val, i)) result = [] while heap: val, index = heapq.heappop(heap) result.append(val) if firstlists[index]: val = firstlists[index].val firstlists[index] = firstlists[index].next heapq.heappush(heap, (val, index)) return result

A concise Python Solution
Basically, you need to quickly lookup to the left, what is the closest column whose height is smaller than you (so a rectangle with h=your height can not extend beyond that column). This is done using a stack maintaining nondecreasing order, with indices stored. Also, you should look right. But how to do it in just O(n)? because when you pop stuff in the stack, you are actually exactly finding the closest smaller column in the right direction. It is this column that forces you to be poped out of the stack (due to the nondecreasing order), and you can only be poped out once. so it must be the first one in the right direction that force you to do so.
Anyway, you can record ever such rect and find max of them as follows:
class Solution: # @param height, a list of integer # @return an integer def largestRectangleArea(self, height): if not height: return 0 # using a queue to keep track of left, closest element smaller than current one; and right smallest element smaller than a given one (that is when it is poped out). and save max in each iteration stack=[] maxrect=0 for i in range(len(height)): current=height[i] while stack: if stack[1][1]>current: (index,h,left)=stack.pop() maxrect=max(h*(iindex1)+left,maxrect) elif stack[1][1]==current: stack.pop() else: break if stack: stack.append((i,current,current*(i(stack[1])[0]))) else: stack.append((i,current,current*(i+1))) while stack: (index,h,left)=stack.pop() maxrect=max(h*(len(height)index1)+left,maxrect) return maxrect

RE: My solution does not need a table for palindrome, is it right ? It uses only O(n) space.
this is not divide and conquer. This is DP. looking backwards of what he is doing, he is building the right cut K[i] for all i<n. aid K[n] is min(all valid palindrome(j,n) + K[j]). However , he did it in a very elegant , serial way

RE: My solution does not need a table for palindrome, is it right ? It uses only O(n) space.
this is not divide and conquer. This is DP.
looking backwards of what he is doing, he is building the right cut K[i] for all i<n. aid K[n] is min(all valid palindrome(j,n) + K[j]). However , he did it in a very elegant , serial way