Решение задачи 122 “Лучшее время покупать и продавать акции 2” с LeetCode.
Условие задачи
На вход принимается массив, где каждый i-тый элемент является ценой акции в день i. Необходимо создать алгоритм, который добъется максимального профита ,покупая и продавая акцию.
Замечание: Представьте, что акция всего одна. Соответственно её можно либо продать, либо купить.
пример
1
2
3
4
5
6
7
|
Input: [7,1,5,3,6,4]
Output: 7
Объяснение:
* Покупаем на второй день (цена = 1) и продаем на третий день (цена = 5), профит = 5-1 = 4.
* Покупаем на день 4 (цена = 3) и продаем на день 5 (цена = 6), профит = 6-3 = 3.
Суммарный профит 4 + 3 = 7
|
1
2
3
4
|
Input: [1,2,3,4,5]
Output: 4
Объяснение:
Покупаем на день 1 (цена = 1) и продаем на дент 5 (цена = 5), профит = 5-1 = 4.
|
1
2
3
4
|
Input: [7,6,4,3,1]
Output: 0
Объяснение:
На таких условиях покупать невыгодно, поэтому результат будет 0.
|
Решение
Поиск максимум и минимумов
Идея алгоритма:
Идти по массиву, находя локальный минимум и максимум. Как только находим локальный максимум - считаем профит ( разница максимума и минимум ).
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
|
func maxProfit(prices []int) int {
if len(prices) < 2 {
return 0
}
sum := 0
localMin := prices[0]
localMax := prices[0]
vectorup := prices[1] > prices[0]
for idx := 1; idx < len(prices); idx++ {
if vectorup {
if prices[idx] >= localMax {
localMax = prices[idx]
} else {
sum += localMax - localMin
vectorup = false
localMin = prices[idx]
}
} else {
if prices[idx] <= localMin {
localMin = prices[idx]
} else {
vectorup = true
localMax = prices[idx]
}
}
}
if vectorup && localMax > localMin {
sum += localMax - localMin
}
return sum
}
|
Сложность
По памяти: O(1)
По операциям: O(n)
Жадный алгоритм
Идея алгоритма:
Каждый день проверять - акция дороже ли вчерашнего дня. Если акция дороже, чем вчера - возвращаться во вчерашний день – покуать акцию, потом возвращаться на текущий день и продавать акцию. Таким образом каждый день, когда ация растет в цене – будет добавляться профит.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
func maxProfit(prices []int) int {
if len(prices) < 2 {
return 0
}
sum := 0
for idx := 1; idx < len(prices); idx++ {
if prices[idx] > prices[idx-1] {
sum += prices[idx] - prices[idx-1]
}
}
return sum
}
|
Сложность
По памяти: O(1)
По операциям: O(n)