Best Time to Buy and Sell Stock

+10

ניתנת לך רשימה prices, שבה prices[i] הוא המחיר של מניה אחת ביום i. מותר לך לקנות מניה אחת ביום אחד ולמכור אותה ביום מאוחר יותר. החזר את הרווח הגדול ביותר שאפשר להשיג, או 0 כאשר כל עסקה אפשרית גורמת להפסד.

פונקציה

maxProfit(prices: integer-array) → integer

pricesinteger-array: מחיר המניה בכל יום, לפי הסדר
מחזירהinteger: הרווח הגדול ביותר מקנייה אחת וממכירה מאוחרת יותר, או 0

אילוצים

1 ≤ prices.length ≤ 10⁵
0 ≤ prices[i] ≤ 10⁴
אתה מבצע לכל היותר עסקה אחת, ומוכר ביום מאוחר יותר מהיום שבו קנית.

דוגמאות

קלט: prices = [7, 2, 5, 9, 1, 4]
פלט: 7
הסבר: קנו ביום 1 במחיר 2 ומכרו ביום 3 במחיר 9, לרווח של 7. המחיר הזול ביותר, 1 ביום 4, מגיע אחרי ה־9, ולכן המכירה הטובה ביותר אחריו מניבה רווח של 3 בלבד.

שאלת המשך

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

פתרון

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

נסו כל זוג קנייה ומכירה

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

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

ברשימה של n מחירים יש בערך n²/2 זוגות: 100,000 ימים משמעותם בערך 5 מיליארד פעולות חיסור.

אלגוריתם

הגדר את best ל־0.
עבור על כל יום קנייה buy.
עבור כל אחד מהם, עבור על כל יום מכירה sell שמגיע אחריו.
חשב את prices[sell] פחות prices[buy], ושמור את התוצאה ב־best אם היא גדולה יותר.
החזר את best.

def maxProfit(prices):
    best = 0
    n = len(prices)
    for buy in range(n):
        for sell in range(buy + 1, n):
            best = max(best, prices[sell] - prices[buy])
    return best

מעבר אחד עם המחיר הנמוך ביותר עד כה

האינטואיציה

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

המעבר קורא כל מחיר פעם אחת ושומר שני מספרים, lowest ו-best: זמן O(n) וזיכרון O(1).

אלגוריתם

הגדירו את lowest למחיר הראשון ואת best ל־0.
עברו על המחירים לפי הסדר.
אם המחיר הנוכחי נמוך מ־lowest, הפכו אותו לערך החדש של lowest.
חשבו את המחיר הנוכחי פחות lowest, ושמרו אותו ב־best אם הוא גדול יותר.
החזירו את best.

def maxProfit(prices):
    lowest = prices[0]
    best = 0
    for price in prices:
        if price < lowest:
            lowest = price
        elif price - lowest > best:
            best = price - lowest
    return best

מלכודות ומקרי קצה

החזרת המחיר הגבוה ביותר פחות המחיר הנמוך ביותר. ב־[7, 2, 5, 9, 1, 4] התוצאה היא 8, אבל 1 מופיע אחרי 9. התשובה היא 7.
לאפשר לתשובה להיות שלילית. ב־[9, 7, 4, 3, 1] ההפרש הטוב ביותר הוא ‎-1; אתחלו את best ל־0, ולא להפרש הראשון.
לאתחל את lowest ל־0. אז כל רווח שווה למחיר עצמו, ולכן [9, 7, 4, 3, 1] מחזיר 9. אתחלו אותו למחיר הראשון.

שאלות נפוצות3

מהי סיבוכיות הזמן של Best Time to Buy and Sell Stock?

הפתרון במעבר יחיד דורש זמן O(n) עבור n ימים, כי הוא קורא כל מחיר פעם אחת, ומקום נוסף O(1): המחיר הנמוך ביותר עד כה והרווח הטוב ביותר. בדיקת כל זוג ימים דורשת זמן O(n²).

למה לא לחסר את המחיר הנמוך ביותר מהמחיר הגבוה ביותר?

המחיר הנמוך ביותר עשוי להגיע אחרי המחיר הגבוה ביותר, ועליך לקנות לפני שאתה מוכר. ב־[7, 2, 5, 9, 1, 4] ה־1 מגיע אחרי ה־9, לכן העסקה הטובה ביותר המותרת קונה ב־2 ומוכרת ב־9, ברווח של 7.

האם "הזמן הטוב ביותר לקנות ולמכור מניה" היא בעיית תכנות דינמי?

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

def maxProfit(prices):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

ארגומנט

prices = [7, 2, 5, 9, 1, 4]

הפלט הצפוי