Най-доброто време за покупка и продажба на акции с решение за такса за транзакции Leetcode


Ниво на трудност M
Често задавани в Амазонка
Array Динамично програмиране Лаком

Изявление на проблема

В проблема „Най-доброто време за купуване и продажба на акции с такса за транзакция“, ни се дава масив, където всеки елемент в масива съдържа цената на дадената акция за този ден.

Дефиницията на транзакция купува една акция от акции и продава тази акция от акции.

Нашата задача е да намерим максималната печалба при следните ограничения:

  1. Не можем да закупим нова акция, ако не сме продали предишната. тоест в даден момент можем да имаме най-много един запас.
  2. Можем да правим множество транзакции.
  3. Всеки път, когато правим транзакция, трябва да платим такси за транзакции.
  4. В даден момент не можем да купим повече от една акция.

Пример

prices = [1, 3, 2, 8, 4, 9], fee=2
8

Обяснение: максималната печалба, която може да бъде получена, е 8. Следват подробностите за сделката:

Най-доброто време за покупка и продажба на акции с решение за такса за транзакции Leetcode

Подходът на най-доброто време за купуване и продажба на акции с решение за такса за транзакция Leetcode Solution

За да разрешим този проблем, трябва да помислим как можем да увеличим максимално печалбата чрез покупка и продажба на акции. Това са начини за постигане на максимална печалба:

  1. Ще закупим акциите на минимална цена и ще продадем на максимална цена.
  2. Тъй като трябва да платим такса за всяка транзакция, ще продадем акциите само когато продажната цена> себестойност + такса.
  3. Въпреки търсенето на най-добрата продажна цена, ние ще продадем акциите, когато срещнем продажна цена> себестойност + такса. Тогава себестойността ще се превърне в себестойност.

изпълнение

C ++ код за най-добро време за купуване и продажба на акции с такса за транзакция

//function to find maximum profit
#include <bits/stdc++.h> 
using namespace std; 
    int Profit(vector<int>& prices, int fee) {
        int n = prices.size();
        int ans = 0;
        int mn = prices[0];
        for(int i=0;i<n;i++)
        {
         if (prices[i] < mn)
                mn = prices[i];
         if(prices[i] > mn + fee)
         {
              ans += prices[i] - fee - mn;
              mn = prices[i] - fee;
         }
            
        }
           return ans;  
    }

int main() 
{ 
 vector<int> arr = {1, 3, 2, 8, 4, 9}; 
 int fee=2;
 cout<<Profit(arr,fee)<<endl; 
 return 0;
}
8

Java код за най-добро време за купуване и продажба на акции с такса за транзакция

import java.util.Arrays; 
public class Tutorialcup {
 public static  int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int ans = 0;
        int mn = prices[0];
        for(int i=0;i<n;i++)
        {
         if (prices[i] < mn)
                mn = prices[i];
         if(prices[i] > mn + fee)
         {
              ans += prices[i] - fee - mn;
              mn = prices[i] - fee;
         }
            
        }
           return ans;  
    }
  public static void main(String[] args) {
    int [] arr = {1, 3, 2, 8, 4, 9}; 
    int fee=2;
    int ans=  maxProfit(arr,fee);
    System.out.println(ans);
  }
}
8

Анализ на сложността на най-доброто време за покупка и продажба на акции с решение за такса за транзакция Leetcode

Времева сложност

Сложността във времето на горния код е О (п) защото обхождаме ценовия масив само веднъж. Тук n е дължината на ценовия масив.

Космическа сложност

O (1) защото използваме памет само за съхраняване на отговора.

Препратки