Најбоље време за куповину и продају залиха помоћу решења за охлађивање Леетцоде-а


Ниво тешкоће Средњи
Често питани у адобе амазонка Голдман Сакс иахоо
Динамичко програмирање

Изјава о проблему

У проблему „Најбоље време за куповину и продају залиха са хлађењем“ добијамо низ где сваки елемент у низу садржи цену дате акције тог дана.

Не постоји ограничење броја трансакција. Дефиниција трансакције је куповина једне акције и продаја те акције.

Наш задатак је да пронађемо максималан профит под следећим ограничењима:

  1. не можемо купити нову залиху ако нисмо продали претходну залиху. то јест у то време можемо имати највише једну залиху.
  2. ако продајемо залиху и-ог дана, не можемо купити акције на (и + 1) -ти дан. То је 1 дан периода хлађења

Пример

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

objašnjenje: максимални профит који се може добити је 3. Следи детаљ трансакције:

Први дан: купи

Други дан: продај

Трећи дан: цоолдовн

Четврти дан: купи

Пети дан: продај

Приступ за најбоље време за куповину и продају залиха помоћу решења за охлађивање Леетцоде-а

Да бисмо решили овај проблем, морамо забележити неколико ствари:

  1. Кад год желимо да продамо деоницу, морали смо да смо је купили раније. Начин продаје акције зависи од куповине акције.
  2. Један дан периода хлађења је неопходан. Дакле, куповина деоница зависи од периода хлађења.

Имајући на уму ове тачке можемо дефинисати стања:

  • ДРЖАВА-А: У овом стању можемо или купити акције или се једноставно одморити.
  • СТАЊЕ-Б: Након куповине акције можемо или продати дионицу или једноставно узети остатак.
  • СТАТЕ-Ц: Ово је стање хлађења. Када се заврши период хлађења прелазимо у СТАТЕ-А.

Најбоље време за куповину и продају деоница са цоолдовном

Однос између ове три државе може се претворити у алгебарски израз где СТАТЕ-Кс [и] представља максимални профит до и-ог дана у стању к.

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];

Након н итерације, максималан профит ће бити мак (са [н-1], сц [н-1]), јер, како желимо да максимизирамо профит, тако нећемо на крају купити или продати деоницу.

Основни случајеви:

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

Имплементација

Ц ++ код за најбоље време за куповину и продају залиха са цоолдовном

#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

Јава код за најбоље време за куповину и продају залиха са цоолдовном

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

Анализа сложености најбољег времена за куповину и продају залиха помоћу решења за охлађивање Леетцоде-а

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

Временска сложеност горњег кода је Он) јер само једном прелазимо низ цена. Овде је н дужина низа цена.

Свемирска сложеност

Сложеност простора горњег кода је Он) јер користимо низ за чување података различитих стања.

Референце