Best Time to Buy and Sell Stock

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

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

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

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

אילוצים: 1 ≤ prices.length ≤ 10^5, 0 ≤ prices[i] ≤ 10^4.