This article is going to explain the Best Time to Buy and Sell Stock series on LeetCode. The following is the relative link:
121 Best Time to Buy and Sell Stock
122 Best Time to Buy and Sell Stock II
309 Best Time to Buy and Sell Stock with Cooldown
714 Best Time to Buy and Sell Stock with Transaction Fee
123 Best Time to Buy and Sell Stock III
188 Best Time to Buy and Sell Stock IV
Best Time to Buy and Sell Stock
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1:


Example 2:


Because we are only permitted to complete at most one transaction, the problem becomes find the largest gap among the array max(xixj), i > j.


Best Time to Buy and Sell Stock II
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. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Because it allows multiple transaction as we like, so, when the gap between each time is greater than zero, we should do a transaction. And the logic is slightly simple:


Best Time to Buy and Sell Stock with Cooldown
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. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
 You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
 After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:


This problem can be solved by State Machine thinking. And I learned this problem the leetcode Discussion
We can know that s0 can be only obtained by rest at itself or rest from s2, s1 and be only obtained by rest at itself or buy from s0, s2 can be obtained only by sell product from s1.
So we will have:


We know that s1 will never be the largest state, because it buy(cost money) and remain same must be smaller than s0. So, the maximum state must among s0 or s2.


Best Time to Buy and Sell Stock with Transaction Fee
Your are given an array of integers prices
, for which the i
th element is the price of a given stock on day i
; and a nonnegative integer fee
representing a transaction fee.
You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)
Return the maximum profit you can make.
Example 1:


This problem is similar to the Problem II, the difference if we have more transactions, we may cost more fees which may decrease the total profit. So, when calculating the cash, we need to consider that fee. The following is the code, and I will explain it with comment:


Line 4 stands for the current profit we have, hold+prices[i]fee
means the profit we have after do a transaction. Compare this the current cash.
Line 5 stands for the hold money, which means we do a buy a product.
Best Time to Buy and Sell Stock III
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. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
The following code is explained with comment:


Best Time to Buy and Sell Stock IV
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. You may complete at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
The idea is almost same as the previous one, but we need to extend it to a two dimension int array rather than store in four variables. And another thing we need to notice is if k >= n/2
, the problem will be the same as II problem, because the limit of transactions will not be a constraint for us. And the code is as follow:


All done with Best Time to Buy and Sell Stock problem. :) Hope you can have a good understanding of Dynamic Programming in this problem. :D Any questions, please leave a comment below. :)