Вақти беҳтарин барои харид ва фурӯш бо саҳмия бо Cooldown Leetcode Solution


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Adobe Amazon Голдман Sachs Yahoo
Барномарезии динамикӣ

Изҳороти мушкилот

Дар масъалаи "Вақти беҳтарини харидан ва фурӯхтани саҳмияҳо бо сардшавии вақт" ба мо массиви дода шудааст, ки дар он ҳар як унсури массив нархи саҳмияҳои дар он рӯзбударо дар бар мегирад.

Дар шумораи амалиётҳо маҳдудият вуҷуд надорад. Таърифи амалиёт хариди як саҳмия ва фурӯши он як саҳмия мебошад.

Вазифаи мо аз он иборат аст, ки дар доираи маҳдудиятҳои зерин фоидаи ҳадди аксарро пайдо кунем:

  1. агар мо саҳмияҳои қаблиро нафурӯшем, мо саҳмияи нав харида наметавонем. ки дар як вақт мо метавонем ҳадди аксар як саҳмия дошта бошем.
  2. агар мо саҳмияҳоро дар рӯзи фурӯшем, пас дар рӯзи (i + 1) саҳмия харида наметавонем. Ин 1 рӯзи давраи сарпӯшӣ аст

мисол

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

Шарҳ: фоидаи ниҳоӣ, ки ба даст овардан мумкин аст, 3. Тафсилоти амалиёт дар зер оварда шудааст:

Рӯзи аввал: харидан

Рӯзи дуюм: фурӯш

Рӯзи сеюм: сарпӯшӣ

Рӯзи чорум: харидан

Рӯзи панҷум: фурӯш

Равиш барои вақти беҳтарин барои харид ва фурӯши саҳҳомӣ бо Cooldown Leetcode Solution

Барои ҳалли ин мушкилот мо бояд чанд чизро қайд намоем:

  1. Ҳар вақте ки мо мехоҳем саҳмияҳоро фурӯшем, мо бояд саҳмияҳоро пештар харида мегирифтем. Воситаҳои фурӯши саҳмия аз хариди саҳмия вобаста аст.
  2. Як рӯзи давраи хунуккунӣ ҳатмист. Аз ин рӯ, хариди саҳмия аз давраи пӯшиш вобаста аст.

Бо дарназардошти ин нуктаҳо, мо метавонем давлатҳоро муайян кунем:

  • ДАВЛАТ-A: Дар ин ҳолат, мо метавонем саҳмия харем ё танҳо истироҳат кунем.
  • ДАВЛАТ-Б: Пас аз харидани саҳмия, мо метавонем саҳмияҳоро фурӯшем ё боқимондаро гирем.
  • ДАВЛАТ-C: Ин як ҳолати сарпӯшӣ аст. Пас аз ба итмом расидани давраи хунуккунӣ мо ба ДАВЛАТИ-A мегузарем.

Вақти беҳтарини харидан ва фурӯхтани саҳмияҳо бо вақти сард

Муносибати байни ин се давлатро ба ифодаи алгебравӣ ки дар он ДАВЛАТ-X [i] фоидаи ҳадди аксарро то рӯзи i дар ҳолати х ифода мекунад.

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 такрор, фоидаи ҳадди аксар max (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 барои вақти беҳтарин барои харидан ва фурӯхтани саҳмияҳо бо вақти хунук

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 Solution

Мураккабии вақт

Мураккабии вақти рамзи боло дар он аст Эй (н) зеро мо массиви нархҳоро танҳо як маротиба убур мекунем. Дар ин ҷо n дарозии массиви нархҳо мебошад.

Мураккабии фазо

Мураккабии фазоии рамзи дар боло зикршуда Эй (н) зеро мо массивро барои нигоҳ доштани иттилооти ҳолатҳои гуногун истифода мебарем.

Адабиёт