הזמן הטוב ביותר לרכישה ולמכירת פתרון Leetcode של מלאי III


רמת קושי קשה
נשאל לעתים קרובות Adobe אמזון בעברית
מערך תכנות דינמי

הצהרת בעיה

בבעיה "הזמן הטוב ביותר לקנות ולמכור מניות III", אנו מקבלים מערך שבו כל רכיב במערך מכיל את מחיר המניה הנתונה באותו יום.

ההגדרה של עסקה קונה מניה אחת במניה ומכירת אותה מניה אחת.

המשימה שלנו היא למצוא את הרווח המרבי תחת המגבלות הבאות:

  1. איננו יכולים לקנות מניה חדשה אם לא מכרנו את המניה הקודמת. כלומר, בכל פעם שנוכל להחזיק לכל היותר מניה אחת.
  2. אנחנו יכולים לבצע לכל היותר שתי עסקאות.

דוגמה

prices = [1,2,3,4,5]
4

הסבר: הרווח המקסימלי שניתן להשיג הוא 4. להלן פירוט העסקה:

יום ראשון: לקנות

יום שני: מנוחה

היום השלישי: מנוחה

היום הרביעי: מנוחה

היום החמישי: למכור

הגישה לזמן הטוב ביותר לרכישה ולמכירת פתרון Leetcode של מלאי III

בעיה זו היא גרסה קשה יותר של הזמן הטוב ביותר לקנות ולמכור מניות. אז חייבים לפתור את הגרסה הקלה של הבעיה לפני שקופצים לבעיה זו.

בהשוואה לגרסה הקלה בה אנו יכולים לבצע רק עסקה אחת כאן, אנו יכולים לבצע לכל היותר שתי עסקאות. שמשמעותו או עסקה אחת או שתי עסקאות באופן כזה שנותן רווח מקסימלי.

החלק המסובך ביותר בבעיה הוא כיצד לטפל בעסקה השנייה. ניתן להמיר בעיה זו לגרסה קלה של בעיה זו, ברגע שנשנה את נקודת המבט שלנו לראות בעיה זו.

נניח שהשלמנו את העסקה הראשונה שלנו ברווח של 200 רופי. (חלק זה זהה ל הזמן הטוב ביותר לקנות ולמכור מניות). אז אחרי העסקה הראשונה, יש לנו 200 שקל ביד.

עכשיו כשאנחנו הולכים לקנות מניה של 500 רופי. אנחנו יכולים לחשוב על זה, אם כי מחיר המניה הוא 500 רופי. אבל מבחינתנו זה 300 רופי כי כבר יש לנו 200 ריש בידיים וקיבלנו את זה בחינם. כעת נבצע את העסקה השנייה בצורה כזו למקסם את הרווח הנקי באותו אופן כמו שעשינו הזמן הטוב ביותר לקנות ולמכור מניות בעיה.

הגישה תהיה ברורה יותר מדוגמה זו:

פתרון leetcode לזמן הטוב ביותר לקנות ולמכור מלאי III

יישום

קוד Java לזמן הטוב ביותר לקנות ולמכור מלאי III

import java.util.Arrays; 
public class Tutorialcup {
    public static int maxProfit(int[] prices) {
  int firstSell = 0;
  int secondSell = 0;
  int firstBuy = Integer.MAX_VALUE;
  int secondBuy = Integer.MAX_VALUE;
  for(int i = 0; i < prices.length; i++) {
    int p = prices[i];
    firstBuy = Math.min(firstBuy, p);
    firstSell = Math.max(firstSell, p - firstBuy);
    secondBuy = Math.min(secondBuy, p - firstSell);
    secondSell = Math.max(secondSell, p - secondBuy);
  }
  
  return secondSell;
    }
  public static void main(String[] args) {
    int [] arr = {1,2,3,4,5}; 
    int ans=  maxProfit(arr);
    System.out.println(ans);
  }
}
4

קוד C ++ לזמן הטוב ביותר לקנות ולמכור מלאי III

#include <bits/stdc++.h> 
using namespace std; 
     int maxProfit(vector<int>& prices) {
  int firstSell = 0;//stores profit after one sell
  int secondSell = 0;//stores profit after two sell
  int firstBuy = INT_MAX;
  int secondBuy = INT_MAX;
  int n=prices.size();
        for(int i=0;i<n;i++)
        {
            firstBuy=min(firstBuy,prices[i]);
            firstSell=max(firstSell,prices[i]-firstBuy);
            secondBuy=min(secondBuy,prices[i]-firstSell);
            secondSell=max(secondSell,prices[i]-secondBuy); 
        }
        return secondSell;
    }
int main() 
{ 
 vector<int> arr = { 1,2,3,4,5 }; 
 cout<<maxProfit(arr)<<endl; 
 return 0;
}
4

ניתוח מורכבות הזמן הטוב ביותר לרכישה ומכירה של פתרון Leetcode III

מורכבות זמן

מורכבות הזמן של הקוד הנ"ל היא O (n) כי אנחנו חוצים את מערך המחירים רק פעם אחת. כאן n הוא אורך מערך המחירים.

מורכבות חלל

מורכבות החלל של הקוד הנ"ל היא O (1) כי אנו משתמשים בזיכרון רק כדי לאחסן את התשובה.

הפניות