Գնման և վաճառքի լավագույն ժամանակը գործարքների վարձի Leetcode լուծմամբ


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon
Դասավորություն Դինամիկ ծրագրավորում Ագահ

Խնդրի հայտարարություն

«Գործարքի վճարով ֆոնդային ֆոնդերի առք ու վաճառքի լավագույն ժամանակը» խնդրում մեզ տրվում է զանգված, որտեղ զանգվածի յուրաքանչյուր տարր պարունակում է տվյալ բաժնետոմսի գին այդ օրը:

Սահմանումը գործարքը գնում է մեկ բաժնետոմսի բաժնետոմս և վաճառում այդ մեկ բաժնետոմս:

Մեր խնդիրն է գտնել առավելագույն շահույթը հետևյալ սահմանափակումների ներքո.

  1. Մենք չենք կարող գնել նոր բաժնետոմս, եթե չենք վաճառել նախորդ բաժնետոմսերը: դա այն ժամանակ, երբ մենք կարող ենք ունենալ առավելագույնը մեկ բաժնետոմս:
  2. Մենք կարող ենք կատարել բազմաթիվ գործարքներ:
  3. Ամեն անգամ, երբ մենք գործարք կկատարենք, մենք պետք է վճարենք գործարքի վճարներ:
  4. Միաժամանակ մենք չենք կարող գնել մեկից ավելի բաժնետոմս:

Օրինակ

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

Բացատրությունը. առավելագույն շահույթը, որը կարելի է ձեռք բերել, կազմում է 8. Հետևյալը գործարքի մանրամասներն են.

Գնման և վաճառքի լավագույն ժամանակը գործարքների վարձի Leetcode լուծմամբ

Գնման և վաճառքի լավագույն ժամանակի մոտեցումը գործարքի վարձի Leetcode լուծմամբ

Այս խնդիրը լուծելու համար մենք պետք է մտածենք, թե ինչպես կարող ենք առավելագույն շահույթ ստանալ `բաժնետոմսեր գնելով և վաճառելով: Սրանք առավելագույն շահույթ ստանալու եղանակներ են.

  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 լուծմամբ

Timeամանակի բարդությունը

Վերոնշյալ ծածկագրի ժամանակի բարդությունն է O (n) քանի որ մենք միայն մեկ անգամ ենք անցնում գների զանգվածը: Այստեղ n- ը գնի զանգվածի երկարությունն է:

Տիեզերական բարդություն

Ո (1) քանի որ մենք հիշողությունը օգտագործում ենք միայն պատասխանը պահելու համար:

Սայլակ