# Best Time to Buy and Sell Stocks

Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one.

# House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

#### Circle Neighbourhood

Problem can simply be decomposed into two House Robber problems: since house 0 and n-1 are now neighbors, at least one of house 0 and n-1 must be safe in one night, which is equivalent to the maximum of

• rob(1, n-1)
• rob(0, n-2)

#### Binary Tree Neighbourhood

There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

# Paint House

#### Min Cost 3 Colors

For n houses, each house can be painted with one of the three colors (0, 1, 2). No two adjacent houses have the same color. The cost of painting each house with a certain color is represented in a n*3 matrix costs.