أفضل وقت لشراء وبيع الأسهم مع Cooldown Leetcode Solution


مستوى الصعوبة متوسط
كثيرا ما يطلب في أدوبي أمازون جولدمان ساكس ياهو
البرمجة الديناميكية

بيان المشكلة

في مشكلة "أفضل وقت لشراء وبيع الأسهم مع فترة التباطؤ" ، يتم منحنا مصفوفة حيث يحتوي كل عنصر في المصفوفة على سعر السهم المحدد في ذلك اليوم.

لا توجد قيود على عدد المعاملات. تعريف الصفقة هو شراء سهم واحد وبيع ذلك السهم.

مهمتنا هي إيجاد أقصى ربح في ظل القيود التالية:

  1. لا يمكننا شراء سهم جديد إذا لم نقم ببيع المخزون السابق. هذا في وقت يمكننا فيه الحصول على مخزون واحد على الأكثر.
  2. إذا قمنا ببيع الأسهم في اليوم الثالث ، فلا يمكننا شراء الأسهم في اليوم (i + 1). هذا هو يوم واحد من فترة التهدئة

مثال

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

التفسير: أقصى ربح يمكن الحصول عليه هو 3. فيما يلي تفاصيل الصفقة:

اليوم الأول: شراء

اليوم الثاني بيع

اليوم الثالث: التهدئة

اليوم الرابع: شراء

اليوم الخامس البيع

نهج أفضل وقت لشراء وبيع الأسهم باستخدام حل Cooldown Leetcode

لحل هذه المشكلة ، نحتاج إلى تدوين بعض الأشياء:

  1. عندما نريد بيع سهم ، يجب أن نكون قد اشترينا السهم في وقت سابق. يعني أن بيع الأسهم يعتمد على شراء السهم.
  2. يوم واحد من فترة التهدئة أمر لا بد منه. لذا فإن شراء الأسهم يعتمد على فترة التبريد.

مع الأخذ في الاعتبار هذه النقاط ، يمكننا تحديد الحالات:

  • STATE-A: في هذه الحالة ، يمكننا إما شراء سهم أو أخذ قسط من الراحة.
  • الحالة ب: بعد شراء السهم يمكننا إما بيع السهم أو ببساطة أخذ الباقي.
  • STATE-C: هذه حالة تهدئة. بمجرد انتهاء فترة التهدئة ، ننتقل إلى STATE-A.

أفضل وقت لشراء وبيع الأسهم مع فترة التهدئة

يمكن تحويل العلاقة بين هذه الحالات الثلاث إلى ملف تعبير جبري حيث تمثل STATE-X [i] أقصى ربح حتى اليوم ith في الحالة 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 ++ لأفضل وقت لشراء وبيع الأسهم مع فترة التهدئة

#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

تحليل التعقيد لأفضل وقت لشراء وبيع الأسهم باستخدام حل Cooldown Leetcode

تعقيد الوقت

التعقيد الزمني للشفرة أعلاه O (ن) لأننا نجتاز مصفوفة الأسعار مرة واحدة فقط. هنا n هو طول مصفوفة الأسعار.

تعقيد الفضاء

تعقيد الفضاء من الكود أعلاه O (ن) لأننا نستخدم مصفوفة لتخزين معلومات حالات مختلفة.

المراجع