Рубрики

Максимальная прибыль при покупке и продаже акций не более k раз

В торговле акциями покупатель покупает акции и продает их в будущем. Учитывая цену акций в течение n дней, трейдеру разрешено совершить не более k транзакций, при этом новая транзакция может начаться только после завершения предыдущей транзакции, узнать максимальную прибыль, которую мог бы получить трейдер.
Примеры:

Input:  
Price = [10, 22, 5, 75, 65, 80]
    K = 2
Output:  87
Trader earns 87 as sum of 12 and 75
Buy at price 10, sell at 22, buy at 
5 and sell at 80

Input:  
Price = [12, 14, 17, 10, 14, 13, 12, 15]
    K = 3
Output:  12
Trader earns 12 as the sum of 5, 4 and 3
Buy at price 12, sell at 17, buy at 10 
and sell at 14 and buy at 12 and sell
at 15
 
Input:  
Price = [100, 30, 15, 10, 8, 25, 80]
    K = 3
Output:  72
Only one transaction. Buy at price 8 
and sell at 80.

Input:  
Price = [90, 80, 70, 60, 50]
    K = 1
Output:  0
Not possible to earn. 

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

В этом посте нам разрешено совершать не более k транзакций. Проблема может быть решена с помощью динамического программирования.

Пусть прибыль [t] [i] представляет максимальную прибыль, используя не более t транзакций до дня i (включая день i). Тогда отношение это:

прибыль [t] [i] = max (прибыль [t] [i-1], max (цена [i] — цена [j] + прибыль [t-1] [j]))
для всех j в диапазоне [0, i-1]

прибыль [т] [я] будет максимум —

  1. Прибыль [т] [я-1], которая представляет не делать никаких транзакций в i-й день.
  2. Максимальная прибыль, полученная от продажи в i-й день. Чтобы продать акции в i-й день, нам необходимо приобрести их в любой из [0, i — 1] дней. Если мы купим акции в j-й день и продадим их в i-й день, максимальная прибыль будет равна цене [i] — цене [j] + прибыли [t-1] [j], где j изменяется от 0 до i-1. Здесь прибыль [t-1] [j] лучше, чем мы могли бы сделать с одной меньшей транзакцией до j-го дня.

Ниже приведена реализация на основе динамического программирования.

C ++

// C ++ программа для определения максимальной прибыли
// покупка и продажа акций максимум k раз
// заданная цена акций за n дней
#include <climits>
#include <iostream>

using namespace std;

  
// Функция определения максимальной прибыли при покупке
// и продаем акцию максимум k раз от данной акции
// цена n дней

int maxProfit(int price[], int n, int k)

{

    // таблица для хранения результатов подзадач

    // profit [t] [i] сохраняет максимальную прибыль, используя

    // максимум t транзакций до дня i (включая

    // день я)

    int profit[k + 1][n + 1];

  

    // В день 0 вы не можете зарабатывать деньги

    // независимо от того, сколько раз вы торгуете

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

        profit[i][0] = 0;

  

    // прибыль равна 0, если мы не делаем никаких переходов

    // (т.е. k = 0)

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

        profit[0][j] = 0;

  

    // заполняем таблицу снизу вверх

    for (int i = 1; i <= k; i++) {

        for (int j = 1; j < n; j++) {

            int max_so_far = INT_MIN;

  

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

                max_so_far = max(max_so_far,

                                 price[j] - price[m] + profit[i - 1][m]);

  

            profit[i][j] = max(profit[i][j - 1], max_so_far);

        }

    }

  

    return profit[k][n - 1];

}

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

int main()

{

    int k = 2;

    int price[] = { 10, 22, 5, 75, 65, 80 };

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

  

    cout << "Maximum profit is: "

         << maxProfit(price, n, k);

  

    return 0;

}

Джава

// Java программа, чтобы узнать максимум
// прибыль от покупки и продажи
// делиться максимум k раз
// цена акций за n дней

  

class GFG {

      

    // Функция, чтобы узнать

    // максимальная прибыль

    // покупка и продажа

    // делиться максимум k раз

    // заданная цена акций за n дней

    static int maxProfit(int[] price, 

                         int n, 

                         int k)

    {

          

        // таблица для хранения результатов

        // подзадач

        // Прибыль [т] [я] магазинов

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

        // максимум t транзакций вверх

        // до дня я (включая день я)

        int[][] profit = new int[k + 1][n + 1];

  

        // Для дня 0 вы не можете

        // зарабатывать деньги независимо

        // сколько раз вы торгуете

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

            profit[i][0] = 0;

  

        // прибыль равна 0, если мы не

        // сделать любой перевод

        // (т.е. k = 0)

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

            profit[0][j] = 0;

  

        // заполнить таблицу в

        // восходящая мода

        for (int i = 1; i <= k; i++) 

        {

            for (int j = 1; j < n; j++)

            {

                int max_so_far = 0;

  

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

                max_so_far = Math.max(max_so_far, price[j] -

                             price[m] + profit[i - 1][m]);

  

                profit[i][j] = Math.max(profit[i] [j - 1], 

                                              max_so_far);

            }

        }

  

        return profit[k][n - 1];

    }

  

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

    public static void main(String []args)

    {

        int k = 2;

        int[] price = { 10, 22, 5, 75, 65, 80 };

        int n = price.length;

        System.out.println("Maximum profit is: "

                            maxProfit(price, n, k));

    }

}

  
// Этот код предоставлен Аншул Аггарвал.

python3

# Python программа для максимизации прибыли
# выполняя не более k транзакций
# учитывая цены акций за n дней

  
# Функция, чтобы узнать максимальную прибыль по
# покупка и продажа акций максимум k раз
# заданная цена акций за n дней

def maxProfit(prices, n, k):

      

    Подход снизу вверх

    profit = [[0 for i in range(k + 1)]

                 for j in range(n)]

      

    # Прибыль равна нулю для первого

    # день и для нулевых транзакций

    for i in range(1, n):

          

        for j in range(1, k + 1):

            max_so_far = 0

              

            for l in range(i):

                max_so_far = max(max_so_far, prices[i] -

                            prices[l] + profit[l][j - 1])

                              

            profit[i][j] = max(profit[i - 1][j], max_so_far)

      

    return profit[n - 1][k]

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

k = 2

prices = [10, 22, 5, 75, 65, 80]

n = len(prices)

  

print("Maximum profit is:",

       maxProfit(prices, n, k))

  
# Этот код предоставлен vaibhav29498

C #

// C # программа для определения максимальной прибыли
// покупка и продажа акций максимум k раз
// заданная цена акций за n дней

using System;

  

class GFG {

      

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

    // покупка и продажа / акция не более k раз

    // заданная цена акций за n дней

    static int maxProfit(int[] price, int n, int k)

    {

        // таблица для хранения результатов подзадач

        // profit [t] [i] сохраняет максимальную прибыль, используя максимум

        // t транзакций до дня i (включая день i)

        int[, ] profit = new int[k + 1, n + 1];

  

        // В день 0 вы не можете зарабатывать деньги

        // независимо от того, сколько раз вы торгуете

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

            profit[i, 0] = 0;

  

        // прибыль равна 0, если мы не делаем никаких переходов

        // (т.е. k = 0)

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

            profit[0, j] = 0;

  

        // заполняем таблицу снизу вверх

        for (int i = 1; i <= k; i++) {

            for (int j = 1; j < n; j++) {

                int max_so_far = 0;

  

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

                max_so_far = Math.Max(max_so_far, price[j] -

                               price[m] + profit[i - 1, m]);

  

                profit[i, j] = Math.Max(profit[i, j - 1], max_so_far);

            }

        }

  

        return profit[k, n - 1];

    }

  

    // Код драйвера для проверки выше

    public static void Main()

    {

        int k = 2;

        int[] price = { 10, 22, 5, 75, 65, 80 };

  

        int n = price.Length;

  

        Console.Write("Maximum profit is: "

                     maxProfit(price, n, k));

    }

}

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

PHP

<?php
// PHP программа для определения максимальной прибыли
// покупка и продажа акций максимум k раз
// заданная цена акций за n дней

  
// Функция определения максимальной прибыли при покупке
// и продаем акцию максимум k раз от данной акции
// цена n дней

function maxProfit($price, $n, $k)

{

      

    // таблица для хранения результатов подзадач

    // profit [t] [i] сохраняет максимальную прибыль, используя

    // максимум t транзакций до дня i (включая

    // день я)

    $profit[$k + 1][$n + 1] = 0;

      

    // В день 0 вы не можете зарабатывать деньги

    // независимо от того, сколько раз вы торгуете

    for ($i = 0; $i <= $k; $i++)

        $profit[$i][0] = 0;

  

    // прибыль равна 0, если мы не

    // сделать любой перевод

    // (т.е. k = 0)

    for ($j = 0; $j <= $n; $j++)

        $profit[0][$j] = 0;

  

    // заполнить таблицу в

    // восходящая мода

    for ($i = 1; $i <= $k; $i++) {

        for ($j = 1; $j < $n; $j++) {

            $max_so_far = PHP_INT_MIN;

  

            for ($m = 0; $m < $j; $m++)

                $max_so_far = max($max_so_far

                              $price[$j] - $price[$m] +

                              $profit[$i - 1][$m]);

  

            $profit[$i][$j] = max($profit[$i][$j - 1],

                                         $max_so_far);

        }

    }

  

    return $profit[$k][$n - 1];

}

  

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

    $k = 2;

    $price = array (10, 22, 5, 75, 65, 80 );

    $n = sizeof($price);

    echo "Maximum profit is: ". maxProfit($price, $n, $k);

  
// Это предоставлено Mits
?>

Выход :

Maximum profit is: 87

Оптимизированное решение:
Вышеупомянутое решение имеет временную сложность O (kn 2 ). Его можно уменьшить, если мы сможем рассчитать максимальную прибыль, полученную от продажи акций в i-й день в постоянное время.

прибыль [t] [i] = max (прибыль [t] [i-1], max (цена [i] — цена [j] + прибыль [t-1] [j]))
для всех j в диапазоне [0, i-1]

Если мы внимательно заметим,
max (цена [i] — цена [j] + прибыль [t-1] [j])
для всех j в диапазоне [0, i-1]

может быть переписан как,
= цена [i] + max (прибыль [t-1] [j] — цена [j])
для всех j в диапазоне [0, i-1]
= цена [i] + max (prevDiff, прибыль [t-1] [i-1] — цена [i-1])
где prevDiff — это максимум (прибыль [t-1] [j] — цена [j])
для всех j в диапазоне [0, i-2]

Итак, если мы уже вычислили max (прибыль [t-1] [j] — цена [j]) для всех j в диапазоне [0, i-2], мы можем рассчитать его для j = i — 1 в постоянном времени , Другими словами, нам больше не нужно оглядываться в диапазон [0, i-1], чтобы найти лучший день для покупки. Мы можем определить это в постоянном времени, используя ниже пересмотренное соотношение.

прибыль [t] [i] = max (прибыль [t] [i-1], цена [i] + max (prevDiff, прибыль [t-1] [i-1] — цена [i-1])
где prevDiff — это максимум (прибыль [t-1] [j] — цена [j]) для всех j в диапазоне [0, i-2]

Ниже его оптимизированная реализация —

C ++

// C ++ программа для определения максимальной прибыли при покупке
// и / продаем акцию максимум k раз от данной акции
// цена n дней
#include <climits>
#include <iostream>

using namespace std;

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

int maxProfit(int price[], int n, int k)

{

    // таблица для хранения результатов подзадач

    // profit [t] [i] сохраняет максимальную прибыль, используя максимум

    // t транзакций до дня i (включая день i)

    int profit[k + 1][n + 1];

  

    // В день 0 вы не можете зарабатывать деньги

    // независимо от того, сколько раз вы торгуете

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

        profit[i][0] = 0;

  

    // прибыль равна 0, если мы не делаем никаких переходов

    // (т.е. k = 0)

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

        profit[0][j] = 0;

  

    // заполняем таблицу снизу вверх

    for (int i = 1; i <= k; i++) {

        int prevDiff = INT_MIN;

        for (int j = 1; j < n; j++) {

            prevDiff = max(prevDiff,

                           profit[i - 1][j - 1] - price[j - 1]);

            profit[i][j] = max(profit[i][j - 1],

                               price[j] + prevDiff);

        }

    }

  

    return profit[k][n - 1];

}

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

int main()

{

    int k = 3;

    int price[] = { 12, 14, 17, 10, 14, 13, 12, 15 };

  

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

  

    cout << "Maximum profit is: "

         << maxProfit(price, n, k);

  

    return 0;

}

Джава

// Java программа, чтобы узнать максимум
// прибыль от покупки и продажи
// делиться максимум k раз от данной акции
// цена n дней

import java.io.*;

  

class GFG {

      

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

    // покупка и продажа / акция не более k раз

    // заданная цена акций за n дней

    static int maxProfit(int price[], 

                         int n, int k)

    {

          

        // таблица для хранения результатов подзадач

        // profit [t] [i] сохраняет максимальную прибыль

        // используя не более t транзакций в день

        // я (включая день я)

        int profit[][] = new int[k + 1][ n + 1];

  

        // В день 0 вы не можете зарабатывать деньги

        // независимо от того, сколько раз вы торгуете

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

            profit[i][0] = 0;

  

        // прибыль равна 0, если мы ничего не делаем

        // переход (т.е. k = 0)

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

            profit[0][j] = 0;

  

        // заполняем таблицу снизу вверх

        for (int i = 1; i <= k; i++) 

        {

            int prevDiff = Integer.MIN_VALUE;

            for (int j = 1; j < n; j++) 

            {

                prevDiff = Math.max(prevDiff, 

                           profit[i - 1][j - 1] - 

                           price[j - 1]);

                profit[i][j] = Math.max(profit[i][j - 1], 

                               price[j] + prevDiff);

            }

        }

  

        return profit[k][n - 1];

    }

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

public static void main (String[] args) 

    {

        int k = 3;

        int price[] = {12, 14, 17, 10, 14, 13, 12, 15};

  

        int n = price.length;

  

        System.out.println("Maximum profit is: "

                            maxProfit(price, n, k));

    }

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

python3

# Python3 программа, чтобы узнать максимум
# прибыль от покупки и / или продажи доли
# не более k раз с учетом цены акции
количество дней

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

def maxProfit(price, n, k): 

  

    # Таблица для хранения результатов подзадач

    # profit [t] [i] сохраняет максимальную прибыль

    # используя не более t транзакций до

    # день я (включая день я)

    profit = [[0 for i in range(n + 1)] 

                 for j in range(k + 1)] 

  

    # Заполните таблицу снизу вверх

    for i in range(1, k + 1): 

        prevDiff = float('-inf')

          

        for j in range(1, n): 

            prevDiff = max(prevDiff,

                           profit[i - 1][j - 1] - 

                           price[j - 1]) 

            profit[i][j] = max(profit[i][j - 1], 

                               price[j] + prevDiff) 

  

    return profit[k][n - 1

  
Код водителя

if __name__ == "__main__":

  

    k = 3

    price = [12, 14, 17, 10, 14, 13, 12, 15]

    n = len(price) 

  

    print("Maximum profit is:",

           maxProfit(price, n, k)) 

  
# Этот код добавлен
# Ритурай Джайн

C #

// C # программа для определения максимальной прибыли при покупке
// и продаем акцию максимум k раз от данной акции
// цена n дней

using System;

  

class GFG {

      

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

    // покупка и продажа / акция не более k раз

    // заданная цена акций за n дней

    static int maxProfit(int[] price, int n, int k)

    {

        // таблица для хранения результатов подзадач

        // profit [t] [i] сохраняет максимальную прибыль, используя максимум

        // t транзакций до дня i (включая день i)

        int[, ] profit = new int[k + 1, n + 1];

  

        // В день 0 вы не можете зарабатывать деньги

        // независимо от того, сколько раз вы торгуете

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

            profit[i, 0] = 0;

  

        // прибыль равна 0, если мы не делаем никаких переходов

        // (т.е. k = 0)

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

            profit[0, j] = 0;

  

        // заполняем таблицу снизу вверх

        for (int i = 1; i <= k; i++) {

            int prevDiff = int.MinValue;

            for (int j = 1; j < n; j++) {

            prevDiff = Math.Max(prevDiff,

                            profit[i - 1, j - 1] - price[j - 1]);

            profit[i, j] = Math.Max(profit[i, j - 1],

                                price[j] + prevDiff);

            }

        }

  

        return profit[k, n - 1];

    }

  

    // Код драйвера для проверки выше

    public static void Main()

    {

        int k = 3;

        int[] price = {12, 14, 17, 10, 14, 13, 12, 15};

  

        int n = price.Length;

  

        Console.Write("Maximum profit is: "

                     maxProfit(price, n, k));

    }

}

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

PHP

<?php
// PHP программа, чтобы узнать максимум
// прибыль от покупки и продажи
// делиться максимум k раз от данной акции
// цена n дней

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

function maxProfit($price, $n, $k)

{

      

    // таблица для хранения результатов

    // прибыль подзадач [t] [i]

    // сохраняет максимальную прибыль, используя

    // максимум t транзакций до

    // день I (включая день I)

    $profit[$k + 1][$n + 1]=0;

  

    // Для дня 0 вы не можете

    // зарабатывать деньги независимо

    // сколько раз вы торгуете

    for ($i = 0; $i <= $k; $i++)

        $profit[$i][0] = 0;

  

    // прибыль равна 0, если мы не

    // сделать любой перевод

    // (т.е. k = 0)

    for ($j = 0; $j <= $n; $j++)

        $profit[0][$j] = 0;

  

    // заполнить таблицу в

    // восходящая мода

    $prevDiff = NULL;

    for ($i = 1; $i <= $k; $i++) {

        for ($j = 1; $j < $n; $j++) {

            $prevDiff = max($prevDiff, $profit[$i - 1][$j - 1] - 

                                               $price[$j - 1]);

            $profit[$i][$j] = max($profit[$i][$j - 1],

                              $price[$j] + $prevDiff);

        }

    }

    return $profit[$k][$n - 1];

}

  

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

    $k = 3;

    $price = array(12, 14, 17, 10, 

                   14, 13, 12, 15);

    $n = sizeof($price);

    echo "Maximum profit is: "

         , maxProfit($price, $n, $k);

  
// Этот код предоставлен нитин митталь
?>

Выход :

Maximum profit is: 12

Временная сложность вышеупомянутого решения составляет O (kn), а сложность пространства — O (nk). Сложность пространства может быть дополнительно уменьшена до O (n), так как мы используем результат последней транзакции. Но чтобы сделать статью легко читаемой, мы использовали O (kn) пробел.

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

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

Максимальная прибыль при покупке и продаже акций не более k раз

0.00 (0%) 0 votes