Задача.
Дан массив целых чисел prices, где prices[i] - цена на акцию в день i. Вам нужно максимизировать прибыль выбрав один день, когда вы купите одну акцию, а также другой день в будущем, когда вы продадите акцию. В качестве результата нужно вернуть максимальную прибыль, которую можно получить. Если прибыль получить нельзя, то вернуть 0.
Ссылка на leetcode: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/
Пример:
prices = [7,1,5,3,6,4]
Ответ: 5 (Купить по 1, продать по 6).
Решение.
Brute force.
Первое решение, которое приходит в голову, это перебрать все пары, посчитать для каждой прибыль и найти максимальную прибыль. Такое решение работает за O(n^2) по времени и O(1) по памяти.
Перебор пар можно сделать при помощи вложенного цикла:
for (int i = 0; i < prices.length; i++) {
for (int j = i + 1; j < prices.length; j++) {
......
}
}
Тогда прибыль для покупки в день i и продажи в день j:
int profit = prices[j] - prices[i];
И нам нужно найти максимум:
public int maxProfit(int[] prices) {
int maxProfit = Integer.MIN_VALUE;
for (int i = 0; i < prices.length; i++) {
for (int j = i + 1; j < prices.length; j++) {
maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
}
}
return maxProfit > 0 ? maxProfit : 0;
}
Dynamic Programming.
Можно ли улучшить это решение? Да, используя динамическое программирование. Давайте применим bottom-up подход. Для этого нужно разбить задачу на подзадачи, а также установить связь решения подзадач с решением более общей задачи.
В данном случае, такой подзадачей может быть максимальная прибыль, которую мы можем получить, если решим продавать в день i. Тогда решением общей задачи будет максимум из всех таких вариантов (максимум из прибылей, когда мы продаем в день 1, день 2, день 3 и т.д.). Как нам определить максимальную прибыль, которую мы можем получить, если продавать в день i? Очевидно, такая прибыль будет максимальная, когда мы купили в день с минимальной ценой в какой-то день до текущего дня i.
maxProfit(i) = prices[i] - min(prices[j], j = 0, .., i - 1)
Тогда ответ будет максимум из таких прибылей:
maxProfit = max(maxProfit(i), i = 1, .., n - 1)
Для того, чтобы нам снова и снова не перевычислять min(prices[j], j = 0, .., i - 1), мы можем хранить это в переменной minPriceSoFar и обновлять ее по мере итерации по массиву.
Код решения:
public int maxProfit(int[] prices) {
int maxProfit = Integer.MIN_VALUE;
int minPriceSoFar = Integer.MAX_VALUE;
for (int i = 0; i < prices.length; i++) {
minPriceSoFar = Math.min(minPriceSoFar, prices[i]);
int currentProfit = prices[i] - minPriceSoFar;
maxProfit = Math.max(maxProfit, currentProfit);
}
return maxProfit;
}
Решение работает за O(n) по времени и O(1) по памяти.
Top comments (0)