Cooldown Leetcode Solution- ի հետ բաժնետոմսերը գնելու և վաճառելու լավագույն ժամանակը


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Adobe Amazon Goldman Sachs-ը Անտաշ անասուն նողկալի արարած
Դինամիկ ծրագրավորում

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

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

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

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

  1. մենք չենք կարող գնել նոր բաժնետոմս, եթե չենք վաճառել նախորդ բաժնետոմսերը: դա այն ժամանակ, երբ մենք կարող ենք ունենալ առավելագույնը մեկ բաժնետոմս:
  2. եթե մենք վաճառենք բաժնետոմս երկրորդ օրը, ապա չենք կարող բաժնետոմս գնել (i + 1) - րդ օրը: Դա սառեցման ժամանակահատվածի 1 օրն է

Օրինակ

prices = [1,2,3,0,2]
3

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

Առաջին օրը `գնել

Երկրորդ օրը `վաճառել

Երրորդ օր. Cooldown

Չորրորդ օրը `գնել

Հինգերորդ օր ՝ վաճառել

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

Այս խնդիրը լուծելու համար մենք պետք է նշենք մի քանի բան.

  1. Ամեն անգամ, երբ ցանկանում ենք բաժնետոմս վաճառել, մենք պետք է ավելի վաղ գնեինք բաժնետոմս: Բաժնետոմս վաճառելու միջոցները կախված են բաժնետոմս գնելուց:
  2. Հանգստացման ժամանակահատվածի մեկ օրը պարտադիր է: Այսպիսով, բաժնետոմս գնելը կախված է սառեցման ժամանակահատվածից:

Հաշվի առնելով այս կետերը ՝ մենք կարող ենք սահմանել պետությունները.

  • ՊԵՏԱԿԱՆ Ա. Այս նահանգում մենք կարող ենք կամ բաժնետոմս գնել, կամ պարզապես հանգստանալ:
  • ՊԵՏԱԿԱՆ Բ. Բաժնետոմս գնելուց հետո մենք կարող ենք կամ վաճառել բաժնետոմսերը, կամ պարզապես վերցնել մնացածը:
  • ՊԵՏԱԿԱՆ Գ. Սա cooldown վիճակ է: Երբ սառեցման ժամանակաշրջանն ավարտվի, մենք տեղափոխվում ենք ՊԵՏ-Ա.

Cooldown- ով բաժնետոմսեր գնելու և վաճառելու լավագույն ժամանակը

Այս երեք պետությունների փոխհարաբերությունները կարող են վերածվել an- ի հանրահաշվական արտահայտություն որտեղ STATE-X [i] - ը x վիճակում ներկայացնում է առավելագույն շահույթը մինչև երկրորդ օրը:

sa->STATE-A,sb->STATE-B,sc->STATE-C
 sa[i]=max(sa[i-1],sc[i-1]);
 sb[i]=max(sb[i-1],sa[i-1]-prices[i]);
 sc[i]=sb[i-1]+prices[i];

N կրկնումից հետո առավելագույն շահույթը կլինի առավելագույնը (sa [n-1], sc [n-1]), քանի որ, քանի որ մենք ուզում ենք առավելագույն շահույթ ստանալ, այնպես որ վերջում բաժնետոմսեր չգնենք և չվաճառենք:

Հիմնական դեպքեր.

sa[0]=0;
sb[0]=-prices[0]
sc[0]=INT_MIN

Իրականացման

C ++ կոդ Cooldown- ով ֆոնդային բորսա գնելու և վաճառելու լավագույն ժամանակի համար

#include <bits/stdc++.h> 
using namespace std; 
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n<1)return 0;
       int sa[n],sb[n],sc[n];
        sa[0]=0,sb[0]=-prices[0],sc[0]=INT_MIN;
        for(int i=1;i<n;i++)
        {
            sa[i]=max(sa[i-1],sc[i-1]);
            sb[i]=max(sb[i-1],sa[i-1]-prices[i]);
            sc[i]=sb[i-1]+prices[i];
        }
        return max(sa[n-1],sc[n-1]);  
    }
int main() 
{ 
 vector<int> arr = { 1,2,3,0,2 }; 
 cout<<maxProfit(arr)<<endl; 
 return 0;
}
3

Java կոդ `Cooldown- ով ֆոնդային բորսան առնելու և վաճառելու լավագույն ժամանակի համար

import java.util.Arrays; 
public class Tutorialcup {
    public static int  maxProfit(int[] prices) {
          int n=prices.length;
    if(n<1)return 0;
    int[] sa = new int[n];
    int[] sb = new int[n];
    int[] sc = new int[n];
    sa[0] = 0;sb[0] = -prices[0]; sc[0] = Integer.MIN_VALUE;

    for (int i = 1; i < n; ++i) {
      sa[i] = Math.max(sa[i-1],sc[i-1]);
      sb[i] = Math.max(sb[i-1],sa[i-1]-prices[i]);
      sc[i] = sb[i-1]+prices[i];
    }

    return Math.max(sa[n-1],sc[n-1]);  
    }
  public static void main(String[] args) {
    int [] arr = {1,2,3,0,2}; 
    int ans=  maxProfit(arr);
    System.out.println(ans);
  }
}
3

Cooldown Leetcode լուծույթի միջոցով ֆոնդային գնման և վաճառքի լավագույն ժամանակի բարդության վերլուծություն

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

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

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

Վերոնշյալ ծածկագրի տիեզերական բարդությունն է O (n) քանի որ մենք օգտագործում ենք զանգված `տարբեր նահանգների տեղեկատվությունը պահելու համար:

Սայլակ