Лучшее время для покупки и продажи акций

Опубликовано: 20 Сентября, 2022

Тип I: разрешена не более одной транзакции

Учитывая массив Prices[] длины N , представляющий цены акций в разные дни, задача состоит в том, чтобы найти максимально возможную прибыль для покупки и продажи акций в разные дни с использованием транзакций, где разрешена не более одной транзакции.

Примечание: акции должны быть куплены перед продажей.

Примеры:

Input: prices[] = {7, 1, 5, 3, 6, 4]
Output: 5
Explanation:
The lowest price of the stock is on the 2nd day, i.e. price = 1. Starting from the 2nd day, the highest price of the stock is witnessed on the 5th day, i.e. price = 6. 
Therefore, maximum possible profit = 6 – 1 = 5. 

Input: prices[] = {7, 6, 4, 3, 1} 
Output: 0
Explanation: Since the array is in decreasing order, no possible way exists to solve the problem.

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

  • Объявите переменную покупки для хранения стоимости покупки и max_profit для хранения максимальной прибыли.
  • Инициализируйте переменную покупки первым элементом массива цен .
  • Перебрать массив цен и проверить, является ли текущая цена минимальной или нет.
    • Если текущая цена минимальна, то покупайте в этот i -й день.
    • Если текущая цена больше , чем предыдущая покупка, то получите от нее прибыль и максимизируйте max_profit.
  • Наконец, верните max_profit .

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

Выход :

5

Временная сложность: O(N). Где N — размер массива цен.
Вспомогательное пространство: O(1). Мы не используем дополнительное пространство.

Подход 2: Данная проблема может быть решена на основе идеи нахождения максимальной разницы между двумя элементами массива с меньшим номером, стоящим перед большим номером. Следовательно, эту задачу можно свести к нахождению max⁡(prices[j]−prices[i]) для каждой пары индексов i и j, таких что j>i .

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

C++




// C++ program for the above approach
 
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
// Function to find maximum profit possible
// by buying and selling at most one stack
int findMaximumProfit(vector<int>& prices, int i, int k,
                      bool buy, vector<vector<int> >& v)
{
    // If no stock can be chosen
    if (i >= prices.size() || k <= 0)
        return 0;
 
    if (v[i][buy] != -1)
        return v[i][buy];
 
    // If a stock is already bought
    if (buy) {
        return v[i][buy]
               = max(-prices[i]
                         + findMaximumProfit(prices, i + 1,
                                             k, !buy, v),
                     findMaximumProfit(prices, i + 1, k,
                                       buy, v));
    }
 
    // Otherwise
    else {
        // Buy now
        return v[i][buy]
               = max(prices[i]
                         + findMaximumProfit(
                             prices, i + 1, k - 1, !buy, v),
                     findMaximumProfit(prices, i + 1, k,
                                       buy, v));
    }
}
 
// Function to find the maximum
// profit in the buy and sell stock
int maxProfit(vector<int>& prices)
{
 
    int n = prices.size();
    vector<vector<int> > v(n, vector<int>(2, -1));
 
    // buy = 1 because atmost one
    // transaction is allowed
    return findMaximumProfit(prices, 0, 1, 1, v);
}
 
// Driver Code
int main()
{
    // Given prices
    vector<int> prices = { 7, 1, 5, 3, 6, 4 };
 
    // Function Call to find the
    // maximum profit possible by
    // buying and selling a single stock
    int ans = maxProfit(prices);
 
    // Print answer
    cout << ans << endl;
 
    return 0;
}

Java



// Java code for the above approach
import java.util.*;
 
class GFG {
 
    // Function to find maximum profit possible
    // by buying and selling at most one stack
    static int findMaximumProfit(int[] prices, int i, int k,
                                 int buy, int[][] v)
    {
 
        // If no stock can be chosen
        if (i >= prices.length || k <= 0)
            return 0;
 
        if (v[i][buy] != -1)
            return v[i][buy];
 
        // If a stock is already bought
        // Buy now
        int nbuy;
        if (buy == 1)
            nbuy = 0;
        else
            nbuy = 1;
        if (buy == 1) {
            return v[i][buy] = Math.max(
                       -prices[i]
                           + findMaximumProfit(
                               prices, i + 1, k, nbuy, v),
                       findMaximumProfit(prices, i + 1, k,
                                         (int)(buy), v));
        }
 
        // Otherwise
        else {
 
            // Buy now
            if (buy == 1)
                nbuy = 0;
            else
                nbuy = 1;
            return v[i][buy]
                = Math.max(
                    prices[i]
                        + findMaximumProfit(prices, i + 1,
                                            k - 1, nbuy, v),
                    findMaximumProfit(prices, i + 1, k, buy,
                                      v));
        }
    }
 
    // Function to find the maximum
    // profit in the buy and sell stock
    static int maxProfit(int[] prices)
    {
        int n = prices.length;
        int[][] v = new int[n][2];
 
        for (int i = 0; i < v.length; i++) {
            v[i][0] = -1;
            v[i][1] = -1;
        }
 
        // buy = 1 because atmost one
        // transaction is allowed
        return findMaximumProfit(prices, 0, 1, 1, v);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Given prices
        int[] prices = { 7, 1, 5, 3, 6, 4 };
 
        // Function Call to find the
        // maximum profit possible by
        // buying and selling a single stock
        int ans = maxProfit(prices);
 
        // Print answer
        System.out.println(ans);
    }
 
    // This code is contributed by Potta Lokesh
Python3



# Python 3 program for the above approach
 
 
# Function to find maximum profit possible
# by buying and selling at most one stack
def findMaximumProfit(prices, i,  k,
                      buy, v):
 
    # If no stock can be chosen
    if (i >= len(prices) or k <= 0):
        return 0
 
    if (v[i][buy] != -1):
        return v[i][buy]
 
    # If a stock is already bought
    if (buy):
        v[i][buy] = max(-prices[i]
                        + findMaximumProfit(prices, i + 1,
                                            k, not buy, v),
                        findMaximumProfit(prices, i + 1, k,
                                          buy, v))
        return v[i][buy]
 
    # Otherwise
    else:
        # Buy now
        v[i][buy] = max(prices[i]
                        + findMaximumProfit(
            prices, i + 1, k - 1, not buy, v),
            findMaximumProfit(prices, i + 1, k,
                              buy, v))
        return v[i][buy]
 
 
# Function to find the maximum
# profit in the buy and sell stock
def maxProfit(prices):
 
    n = len(prices)
    v = [[-1 for x in range(2)]for y in range(n)]
 
    # buy = 1 because atmost one
    # transaction is allowed
    return findMaximumProfit(prices, 0, 1, 1, v)
 
 
# Driver Code
if __name__ == "__main__":
 
    # Given prices
    prices = [7, 1, 5, 3, 6, 4]
 
    # Function Call to find the
    # maximum profit possible by
    # buying and selling a single stock
    ans = maxProfit(prices)
 
    # Print answer
    print(ans)
C#



// C# program for above approach
using System;
 
class GFG {
 
    // Function to find maximum profit possible
    // by buying and selling at most one stack
    static int findMaximumProfit(int[] prices, int i, int k,
                                 int buy, int[, ] v)
    {
 
        // If no stock can be chosen
        if (i >= prices.Length || k <= 0)
            return 0;
 
        if (v[i, buy] != -1)
            return v[i, buy];
 
        // If a stock is already bought
        // Buy now
        int nbuy;
        if (buy == 1)
            nbuy = 0;
        else
            nbuy = 1;
        if (buy == 1) {
            return v[i, buy] = Math.Max(
                       -prices[i]
                           + findMaximumProfit(
                               prices, i + 1, k, nbuy, v),
                       findMaximumProfit(prices, i + 1, k,
                                         (int)(buy), v));
        }
 
        // Otherwise
        else {
 
            // Buy now
            if (buy == 1)
                nbuy = 0;
            else
                nbuy = 1;
            return v[i, buy]
                = Math.Max(
                    prices[i]
                        + findMaximumProfit(prices, i + 1,
                                            k - 1, nbuy, v),
                    findMaximumProfit(prices, i + 1, k, buy,
                                      v));
        }
    }
 
    // Function to find the maximum
    // profit in the buy and sell stock
    static int maxProfit(int[] prices)
    {
        int n = prices.Length;
        int[, ] v = new int[n, 2];
 
        for (int i = 0; i < n; i++) {
            v[i, 0] = -1;
            v[i, 1] = -1;
        }
 
        // buy = 1 because atmost one
        // transaction is allowed
        return findMaximumProfit(prices, 0, 1, 1, v);
    }
 
    // Driver Code
    public static void Main()
    {
 
        // Given prices
        
                            

                    
                                    

                        

                
РЕКОМЕНДУЕМЫЕ СТАТЬИ