Рубрики

Акции Купить Продать, чтобы максимизировать прибыль

Стоимость акций на каждый день указана в массиве, найдите максимальную прибыль, которую вы можете получить, покупая и продавая в те дни. Например, если указанный массив равен {100, 180, 260, 310, 40, 535, 695}, максимальную прибыль можно получить, купив в день 0, продав в день 3. Снова купите в день 4 и продайте в день 6 Если данный массив цен отсортирован в порядке убывания, то прибыль вообще не может быть заработана.

Наивный подход. Простой подход состоит в том, чтобы пытаться покупать акции и продавать их каждый день, когда это выгодно, и до сих пор обновлять максимальную прибыль.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция возврата максимальной прибыли
// это можно сделать после покупки и
// продажа акций

int maxProfit(int price[], int start, int end)

{

  

    // Если акции нельзя купить

    if (end <= start)

        return 0;

  

    // Инициализируем прибыль

    int profit = 0;

  

    // День, когда акции

    // должен быть куплен

    for (int i = start; i < end; i++) {

  

        // День, в который

        // акции должны быть проданы

        for (int j = i + 1; j <= end; j++) {

  

            // Если на складе в первый день и

            // продать его в j-й день выгодно

            if (price[j] > price[i]) {

  

                // Обновляем текущую прибыль

                int curr_profit = price[j] - price[i]

                                  + maxProfit(price, start, i - 1)

                                  + maxProfit(price, j + 1, end);

  

                // Обновление максимальной прибыли

                profit = max(profit, curr_profit);

            }

        }

    }

    return profit;

}

  
// Код драйвера

int main()

{

    int price[] = { 100, 180, 260, 310,

                    40, 535, 695 };

    int n = sizeof(price) / sizeof(price[0]);

  

    cout << maxProfit(price, 0, n - 1);

  

    return 0;

}

Выход:

865

Эффективный подход: если нам разрешено покупать и продавать только один раз, тогда мы можем использовать следующий алгоритм. Максимальная разница между двумя элементами . Здесь нам разрешено покупать и продавать несколько раз.
Ниже приводится алгоритм для этой проблемы.

  1. Найдите локальные минимумы и сохраните их как начальный индекс. Если не существует, вернитесь.
  2. Найдите локальные максимумы. и сохранить его как конечный индекс. Если мы достигнем конца, установите конец как конечный индекс.
  3. Обновление решения (увеличение числа покупок и продаж пар)
  4. Повторите вышеуказанные шаги, если конец не достигнут.

C ++

// C ++ Программа для поиска лучших дней покупки и продажи
#include <bits/stdc++.h>

using namespace std;

  
// Эта функция находит продажу на покупку
// график максимальной прибыли

void stockBuySell(int price[], int n)

{

    // Цены должны быть указаны как минимум на два дня

    if (n == 1)

        return;

  

    // Пройти через данный ценовой массив

    int i = 0;

    while (i < n - 1) {

  

        // Найти локальные минимумы

        // Обратите внимание, что предел равен (n-2)

        // сравниваем текущий элемент со следующим

        while ((i < n - 1) && (price[i + 1] <= price[i]))

            i++;

  

        // Если мы достигли конца, перерыв

        // как дальнейшее решение невозможно

        if (i == n - 1)

            break;

  

        // Сохраняем индекс минимумов

        int buy = i++;

  

        // Найти локальные максимумы

        // Обратите внимание, что предел равен (n-1)

        // по сравнению с предыдущим элементом

        while ((i < n) && (price[i] >= price[i - 1]))

            i++;

  

        // Сохраняем индекс максимумов

        int sell = i - 1;

  

        cout << "Buy on day: " << buy

             << "\t Sell on day: " << sell << endl;

    }

}

  
// Код драйвера

int main()

{

    // Цены на акции в последующие дни

    int price[] = { 100, 180, 260, 310, 40, 535, 695 };

    int n = sizeof(price) / sizeof(price[0]);

  

    // Функциональный вызов

    stockBuySell(price, n);

  

    return 0;

}

  
// Это код, предоставленный rathbhupendra

С

// Программа для поиска лучших дней покупки и продажи
#include <stdio.h>

  
// структура решения

struct Interval {

    int buy;

    int sell;

};

  
// Эта функция находит график покупки-продажи для получения максимальной прибыли

void stockBuySell(int price[], int n)

{

    // Цены должны быть указаны как минимум на два дня

    if (n == 1)

        return;

  

    int count = 0; // количество пар решений

  

    // вектор решения

    Interval sol[n / 2 + 1];

  

    // Пройти через данный ценовой массив

    int i = 0;

    while (i < n - 1) {

        // Найти локальные минимумы. Обратите внимание, что предел равен (n-2), поскольку мы

        // сравниваем текущий элемент со следующим.

        while ((i < n - 1) && (price[i + 1] <= price[i]))

            i++;

  

        // Если мы достигли конца, сломаемся, так как дальнейшее решение невозможно

        if (i == n - 1)

            break;

  

        // Сохраняем индекс минимумов

        sol[count].buy = i++;

  

        // Найти локальные максимумы. Обратите внимание, что предел равен (n-1), поскольку мы

        // по сравнению с предыдущим элементом

        while ((i < n) && (price[i] >= price[i - 1]))

            i++;

  

        // Сохраняем индекс максимумов

        sol[count].sell = i - 1;

  

        // Увеличение количества покупок / продаж пар

        count++;

    }

  

    // распечатать решение

    if (count == 0)

        printf("There is no day when buying the stock will make profitn");

    else {

        for (int i = 0; i < count; i++)

            printf("Buy on day: %dt Sell on day: %dn", sol[i].buy, sol[i].sell);

    }

  

    return;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // цены на акции в последующие дни

    int price[] = { 100, 180, 260, 310, 40, 535, 695 };

    int n = sizeof(price) / sizeof(price[0]);

  

    // функциональный вызов

    stockBuySell(price, n);

  

    return 0;

}

Джава

// Программа для поиска лучших дней покупки и продажи

import java.util.ArrayList;

  
// Структура решения

class Interval {

    int buy, sell;

}

  

class StockBuySell {

    // Эта функция находит график покупки-продажи для получения максимальной прибыли

    void stockBuySell(int price[], int n)

    {

        // Цены должны быть указаны как минимум на два дня

        if (n == 1)

            return;

  

        int count = 0;

  

        // массив решений

        ArrayList<Interval> sol = new ArrayList<Interval>();

  

        // Пройти через данный ценовой массив

        int i = 0;

        while (i < n - 1) {

            // Найти локальные минимумы. Обратите внимание, что предел равен (n-2), поскольку мы

            // сравниваем текущий элемент со следующим.

            while ((i < n - 1) && (price[i + 1] <= price[i]))

                i++;

  

            // Если мы достигли конца, сломаемся, так как дальнейшее решение невозможно

            if (i == n - 1)

                break;

  

            Interval e = new Interval();

            e.buy = i++;

            // Сохраняем индекс минимумов

  

            // Найти локальные максимумы. Обратите внимание, что предел равен (n-1), поскольку мы

            // по сравнению с предыдущим элементом

            while ((i < n) && (price[i] >= price[i - 1]))

                i++;

  

            // Сохраняем индекс максимумов

            e.sell = i - 1;

            sol.add(e);

  

            // Увеличиваем количество покупок / продаж

            count++;

        }

  

        // распечатать решение

        if (count == 0)

            System.out.println("There is no day when buying the stock "

                               + "will make profit");

        else

            for (int j = 0; j < count; j++)

                System.out.println("Buy on day: " + sol.get(j).buy

                                   + "        "

                                   + "Sell on day : " + sol.get(j).sell);

  

        return;

    }

  

    public static void main(String args[])

    {

        StockBuySell stock = new StockBuySell();

  

        // цены на акции в последующие дни

        int price[] = { 100, 180, 260, 310, 40, 535, 695 };

        int n = price.length;

  

        // функциональный вызов

        stock.stockBuySell(price, n);

    }

}

  
// Этот код предоставлен Mayank Jaiswal


Выход:

Buy on day : 0   Sell on day: 3
Buy on day : 4   Sell on day: 6

Сложность времени: внешний цикл работает, пока я не станет n-1. Внутренние два цикла увеличивают значение i в каждой итерации. Таким образом, общая сложность времени O (n)

Эта статья составлена Ашишем Анандом и рецензирована командой GeeksforGeeks. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Акции Купить Продать, чтобы максимизировать прибыль

0.00 (0%) 0 votes