algorithm

best time to buy and sell stock

1. 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:

1
2
3
4
Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

1
2
3
4
Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

Answer:

for each time i with price = prices[i], we should find the minimum prices whose time j < i 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func MaxProfit(prices []int) int {
	min := math.MaxInt32
	max := 0
	for _, x := range prices {
		temp := x - min
		if temp > max {
			max = temp
		}
		if x < min {
			min = x
		}
	}

	return max
}

2. Best Time to Buy and Sell Stock II

Say you have an array for whichthe ith elementis the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may completeas many transactions as you like (ie, buy one and sell one share of the stockmultiple times). However, you may not engage in multiple transactions at thesame time (ie, you must sell the stock before you buy again).

Example：

Input: [7, 1, 5,3, 6, 4]

Output: 7

Input: [7, 6, 4,3, 1]

Output: 0

Answer:

since we can do many transaction as we want, then we just need find every close valley and peak in the curve.

1
2
3
4
5
6
7
8
9
10
func MaxprofileWithMultitransaction(prices []int) int {
	profile := 0
	for i := 1; i < len(prices); i++ {
		if prices[i] > prices[i-1] {
			profile += prices[i] - prices[i-1]
		}
	}

	return profile
}

3.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).

Answer:

DP problem, prof[i] is the max profile with up to r transactions before time i.

m = max profile with up to r-1 transaction and prices[i] as buying price in the next transaction at time i

prof[i] = max(prof[i-1],prices[i]+m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if prices == nil || len(prices) <= 0 {
		return 0
	}

	n := len(prices)
	prof := make([]int, n, n)
	for r := 0; r < 2; r++ {
		m := prof[0] - prices[0]
		for i := 1; i < len(prices); i++ {
			m = max(m, prof[i]-prices[i])
			prof[i] = max(prof[i-1], prices[i]+m)
		}
	}

	return prof[n-1]

4.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).

Answer:

DP problem 

1
2
prof[r][i] = max(prof[r][i-1],prices[i]+m) // max(profile with no transaction at time i,profile with transaction at time i)
m = max(m,prof[r-1][i-1]-prices[i]) // max profile with r-1 transaction at time i-1 and buying price = prices[i]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// MaxProfitWithKTransactionDP 动态规划版本
// prof[r][j] 表示j时刻，最多r次交易可以获得的最大收益
// m = max(prof[r-1][j-1]-prices[j],m) 表示r-1笔交易情况下，j-1时刻的收益减去j时刻的价格的最大值
// m意义是基于r-1笔交易收益为prof[r-1][t]的前提下，找到一个低点买入，即需要找到一个时刻t，使得prof[r-1][t-1]-prices[t]值最大，这样才能在后续高点卖出，是的整体收益最大化
// 由于交易笔数k可能比较大，远远大于prices的长度，即这样交易笔数不在重要，只要有价差就可以买入卖出，所以当k>len(prices)/2时，可以直接退化至任意笔操作
func MaxProfitWithKTransactionDP(k int, prices []int) int {
	if prices == nil || len(prices) <= 0 {
		return 0
	}

	if k > len(prices)/2 {
		return quickSlove(prices)
	}

	n := len(prices)
	prof := make([][]int, k+1, k+1)
	for i := 0; i < k+1; i++ {
		prof[i] = make([]int, n, n)
	}

	for r := 1; r <= k; r++ {
		m := prof[r][0] - prices[0]
		for i := 1; i < len(prices); i++ {
			prof[r][i] = max(prof[r][i-1], prices[i]+m)
			m = max(m, prof[r-1][i-1]-prices[i])
		}
	}

	return prof[k][n-1]
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func quickSlove(prices []int) int {
	profile := 0
	for i := 1; i < len(prices); i++ {
		if prices[i] > prices[i-1] {
			profile += prices[i] - prices[i-1]
		}
	}
	return profile
}