გარიგების საკომისიო Leetcode Solution- ით ყიდვისა და გაყიდვის საუკეთესო დრო


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon
Array დინამიური პროგრამირება ხარბ

პრობლემის განცხადება

პრობლემის ”გარიგების საფასურის ყიდვისა და გაყიდვის საუკეთესო დრო”, მოცემულია მასივი, სადაც მასივის თითოეული ელემენტი შეიცავს მოცემული აქციის ფასს ამ დღეს.

განმარტება გარიგების ყიდულობს ერთ აქციას და ყიდის ამ ერთ წილს.

ჩვენი ამოცანაა მაქსიმალური მოგების პოვნა შემდეგი შეზღუდვებით:

  1. ჩვენ არ შეგვიძლია ახალი აქციების ყიდვა, თუ წინა აქციები არ გავყიდეთ. ამ დროს ჩვენ შეგვიძლია მაქსიმუმ ერთი მარაგი გვქონდეს.
  2. ჩვენ შეგვიძლია გავაკეთოთ მრავალი ოპერაცია.
  3. ყოველთვის, როდესაც ჩვენ გავაკეთებთ გარიგებას, უნდა გადაიხადოთ ტრანსაქციის საკომისიოები.
  4. იმავდროულად, ერთზე მეტი მარაგის ყიდვა არ შეგვიძლია.

მაგალითი

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

განმარტება: მაქსიმალური მოგება, რომლის მიღებაც არის 8. ქვემოთ მოცემულია გარიგების დეტალები:

გარიგების საკომისიო Leetcode Solution- ით ყიდვისა და გაყიდვის საუკეთესო დრო

ყიდვისა და გაყიდვის საუკეთესო დროის მიდგომა გარიგების საკომისიო 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

ჯავის კოდი ყიდვისა და გაყიდვის საუკეთესო დროისთვის გარიგების საკომისიოსთვის

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 გადაწყვეტილებით

დროის სირთულე

ზემოთ მოცემული კოდის სირთულეა O (n) რადგან ფასის მასივს მხოლოდ ერთხელ ვათვალიერებთ. აქ n არის ფასების მასივის სიგრძე.

კოსმოსური სირთულის

O (1) რადგან მეხსიერებას მხოლოდ პასუხის შესანახად ვიყენებთ.

ლიტერატურა