DEV Community

faangmaster
faangmaster

Posted on • Edited on

Простая задача на динамическое программирование: Лучшее время для покупки и продажи акции

Задача.

Дан массив целых чисел 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++) {
        ......
    }
}
Enter fullscreen mode Exit fullscreen mode

Тогда прибыль для покупки в день 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;
}
Enter fullscreen mode Exit fullscreen mode

Dynamic Programming.

Можно ли улучшить это решение? Да, используя динамическое программирование. Давайте применим bottom-up подход. Для этого нужно разбить задачу на подзадачи, а также установить связь решения подзадач с решением более общей задачи.
В данном случае, такой подзадачей может быть максимальная прибыль, которую мы можем получить, если решим продавать в день i. Тогда решением общей задачи будет максимум из всех таких вариантов (максимум из прибылей, когда мы продаем в день 1, день 2, день 3 и т.д.). Как нам определить максимальную прибыль, которую мы можем получить, если продавать в день i? Очевидно, такая прибыль будет максимальная, когда мы купили в день с минимальной ценой в какой-то день до текущего дня i.

maxProfit(i) = prices[i] - min(prices[j], j = 0, .., i - 1)
Enter fullscreen mode Exit fullscreen mode

Тогда ответ будет максимум из таких прибылей:

maxProfit = max(maxProfit(i), i = 1, .., n - 1)
Enter fullscreen mode Exit fullscreen mode

Для того, чтобы нам снова и снова не перевычислять 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;
}
Enter fullscreen mode Exit fullscreen mode

Решение работает за O(n) по времени и O(1) по памяти.

Image of Datadog

Create and maintain end-to-end frontend tests

Learn best practices on creating frontend tests, testing on-premise apps, integrating tests into your CI/CD pipeline, and using Datadog’s testing tunnel.

Download The Guide

Top comments (0)

Image of Datadog

Master Mobile Monitoring for iOS Apps

Monitor your app’s health with real-time insights into crash-free rates, start times, and more. Optimize performance and prevent user churn by addressing critical issues like app hangs, and ANRs. Learn how to keep your iOS app running smoothly across all devices by downloading this eBook.

Get The eBook