ከቀዝቃዛው ሌቲኮድ መፍትሄ ጋር ክምችት ለመግዛት እና ለመሸጥ የተሻለው ጊዜ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe አማዞን ጎልድማን ሳክስ ያሁ
ተለዋዋጭ ፕሮግራም

የችግር እሴት

በችግር ውስጥ “ከኩልደዋን ጋር አክሲዮን ለመግዛት እና ለመሸጥ” በሚለው ችግር ውስጥ እያንዳንዱ በድርድሩ ውስጥ ያለው እያንዳንዱ ንጥረ ነገር በዚያ ቀን የተሰጠውን የአክሲዮን ዋጋ የሚይዝበት ድርድር ይሰጠናል።

በግብይቶች ብዛት ላይ ምንም ገደብ የለም ፡፡ የግብይቱ ትርጉም አንድ የአክሲዮን ድርሻ በመግዛት ያንን የአክሲዮን ድርሻ መሸጥ ነው ፡፡

የእኛ ተግባር በሚከተሉት ገደቦች ከፍተኛውን ትርፍ ማግኘት ነው-

  1. የቀደመውን አክሲዮን ካልሸጥን አዲስ አክሲዮን መግዛት አንችልም ፡፡ ያ ቢበዛ አንድ ክምችት ሊኖረን በሚችልበት ጊዜ ላይ ነው ፡፡
  2. እኛ ቀን ላይ አንድ አክሲዮን የምንሸጥ ከሆነ በዚያን ቀን (i + 1) ላይ አክሲዮን መግዛት አንችልም። ያ የቀዘቀዘ ጊዜ 1 ቀን ነው

ለምሳሌ

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

ማብራሪያ: ሊገኝ የሚችለው ከፍተኛ ትርፍ 3. የግብይት ዝርዝርን የሚከተለው ነው-

የመጀመሪያ ቀን: ይግዙ

ሁለተኛ ቀን መሸጥ

ሦስተኛው ቀን - የቀዘቀዘ

አራተኛው ቀን: ይግዙ

አምስተኛው ቀን መሸጥ

ከቀዝቃዛው ሌቲኮድ መፍትሄ ጋር ክምችት ለመግዛት እና ለመሸጥ ለተሻለ ጊዜ አቀራረብ

ይህንን ችግር ለመፍታት ጥቂት ነገሮችን ልብ ማለት አለብን ፡፡

  1. አክሲዮን ለመሸጥ በምንፈልግበት ጊዜ ሁሉ ቀደም ሲል አክሲዮኑን ገዝተን መሆን አለብን ፡፡ አክሲዮን መሸጥ ማለት አክሲዮን በመግዛት ላይ የተመሠረተ ነው ፡፡
  2. ከቀዝቃዛው ዘመን አንድ ቀን የግድ አስፈላጊ ነው ፡፡ ስለዚህ አክሲዮን መግዛት በቀዝቃዛው ወቅት ላይ ጥገኛ ነው ፡፡

እነዚህን ነጥቦች ከግምት ውስጥ በማስገባት ግዛቶችን መወሰን እንችላለን ፡፡

  • ስቴት-ሀ-በዚህ ሁኔታ ውስጥ እኛ አንድ አክሲዮን መግዛት ወይም ልክ ማረፍ እንችላለን ፡፡
  • ስቴት-ቢ-አክሲዮን ከገዛን በኋላ አክሲዮኑን መሸጥ ወይም ቀሪውን በቀላሉ መውሰድ እንችላለን ፡፡
  • ስቴት-ሲ-ይህ የቀዝቃዛ ከተማ ነው ፡፡ የቀዝቃዛው ዘመን ጊዜ ካለፈ በኋላ ወደ STATE-A እንሸጋገራለን።

ከኩልደወን ጋር ክምችት ለመግዛት እና ለመሸጥ የተሻለው ጊዜ

በእነዚህ ሶስት ግዛቶች መካከል ያለው ግንኙነት ወደ አንድ ሊለወጥ ይችላል የአልጀብራ አገላለጽ እስቴት-ኤክስ [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-1] ፣ sc [n-1]) ምክንያቱም ፣ ትርፍውን ከፍ ለማድረግ እንደምንፈልግ አክሲዮን ገዝተን አንሸጥም ፡፡

መሰረታዊ ጉዳዮች

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

አፈጻጸም

ከ Coolown ጋር ክምችት ለመግዛት እና ለመሸጥ ለተሻለ ጊዜ C ++ ኮድ

#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

ከቀዝቃዛው ሌቲኮድ መፍትሄ ጋር ክምችት ለመግዛት እና ለመሸጥ የተሻለው ጊዜ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ከላይ ያለው ኮድ የጊዜ ውስብስብነት ነው ሆይ (n) ምክንያቱም የዋጋ ድርድርን አንድ ጊዜ ብቻ ስለምናልፍ ነው። እዚህ n የዋጋ ድርድር ርዝመት ነው።

የቦታ ውስብስብነት

ከላይ ያለው ኮድ የቦታ ውስብስብነት ነው ሆይ (n) ምክንያቱም የተለያዩ ግዛቶችን መረጃ ለማከማቸት አንድ ድርድር እንጠቀማለን።

ማጣቀሻዎች