سوال: لیستی از ارزش هر سهم یک موسسه در یک بازه زمانی داده شده است. با فرض اینکه تنها می توانید یک سهم این موسسه را خرید و فروش کنید، برنامه ای بنویسید که بیشترین سود ممکن از این کار را برگرداند.
پاسخ: ابتدا نیاز داریم که پرسش را بهتر درک کنیم (فهم مساله). با آوردن یک مثال باید مطمین شویم که منظور مصاحبه کننده را درست متوجه شده ایم. این بسیار مهم است که مساله درست را حل کنیم.
فرض کنیم که قیمت سهام یک شرکت فرضی در تعدادی روز متوالی به شکل زیر است.
در این مثال اگر سهم را در روز اول بخریم و همان روز بفروشیم هیچ سودی نکرده ایم. اگر آن را در روز اول بخریم و در روز دوم بفروشیم در واقع دو واحد پولی (ریال - دلار بسته به واحد محور y) ضرر کرده ایم. اگر سهم را روز دوم بخریم و روز چهارم بفروشیم ۵ واحد سود کرده ایم. بیشترین سود از خرید در روز سوم و فروش در روز پنجم بدست می آید. در این صورت مقدار سود 8-18 یا به عبارتی 10 می باشد.
داده های نمودار فوق را همچنین می توانیم در یک لیست مثل لیست زیر قرار دهیم.
در یک مصاحبه، اولین راه حلی که باید مطرح کنیم روش جستجوی کامل است (راه حل جستجوی کامل). جستجوی کامل برای یافتن پاسخ این مساله یعنی همه حالات خرید-فروش را، با در نظر گرفتن هر یک از روزها برای خرید و هریک از روزهای بعد آن برای فروش، بدست آوریم. برای این کار می توانیم از دو حلقه تو در تو استفاده کنیم که شمارنده حلقه بیرونی اندیس روز خرید (متغیر i) و شمارنده حلقه درونی اندیس روز فروش (متغیر j) در لیست را مشخص می کنند. در هر تکرار حلقه بیرونی سراغ یک عنصر می رویم (روز خرید) و برای هر چنین عنصری، با استفاده از حلقه درونی از عنصر بعد آن (i+1) تا آخر لیست (n-1) را تک تک به عنوان روز فروش در نظر می گیریم. برای هر حالت خرید-فروش بوجود آمده، میزان سود را محاسبه می کنیم. خرید-فروشی که بیشترین سود را بدهد پاسخ مساله است. در یک مصاحبه واقعی این روش را بصورت دستی امتحان می کنیم تا مطمین شویم که الگوریتم درست عمل می کند.
برای محاسبه سرعت این الگوریتم (یا بالعکس، پیچیدگی محاسباتی آن) ، باید در نظر بگیریم که هر روز با هر یک از روز های بعدیش یک حالت خرید-فروش را می سازد. اگر تعداد روزهایی که داده های سهام را در آن داریم n باشد آنگاه n*(n-1)/2 حالت خرید-فروش را باید امتحان کنیم. بنابر این پیچیدگی محاسباتی این الگوریتم (O(n^2 می باشد.
الگوریتم جستجوی کامل یک قدم درست برای حل این مساله است. اما مصاحبه کننده از ما میخواهد که راه حل سریع تری بیابیم.
برای پیدا کردن راه حل بهتر باید اندیشیم که راه حل کنونی در واقع چگونه کار می کند و سعی کنیم دلیل کند بودن آن را بیابیم و اصلاح کنیم. با تفکر در مورد نحوه کار الگوریتم جستجوی کامل ارایه شده متوجه می شویم که این الگوریتم در واقع هر بار عنصر ماکزیمم (بزرگترین عنصر) بعد از هر عنصر (بین عناصر i+1 تا n-1) را می یابد. به این ترتیب حداکثر سود ممکن از خرید در هر یک از روزها را بدست می آورد.
با مشاهده روش یافتن عنصر ماکزیمم متوجه می شویم که حلقه دورنی در واقع تکرارهای زیادی را برای یافتن عنصر ماکزیمم بعد از یک عنصر انجام می دهد. این تکرارها چیزی است که کل الگوریتم را n بار (n طول لیست را نشان می دهد) کند می کند. این در حالی است که پس از یافتن ماکزیمم بین عناصر بعد از i (یعنی بین i+1 تا n-1) و برای یافتن ماکزیمم بین عناصر بعد از عنصر i+1 در دور بعد، باید بین عناصر بعدی آن یعنی i+2 تا n-1 به دنبال عنصر ماکزیمم بگردیم. در واقع قسمت عمده ای از لیست که در آن عنصر ماکزیمم قبلی را یافتیم تغییر نمی کند بلکه تنها یک عنصر از ابتدای آن کم می شود (عنصر i+1 را کم می کنیم).
در عین حال متوجه می شویم که راه حل سرراستی برای بدست آوردن مقدار ماکزیمم جدید (بدون محاسبه مجدد) پس از حذف یک عنصر از ابتدای یک لیست نداریم (یافتن ایراد راه حل). در عوض می دانیم که عکس آن یعنی بدست آوردن مقدار ماکزیمم یا مینیمم بعد از افزودن یک عنصر بسیار سر راست و سریع است: در واقع برای یافتن ماکزیمم جدید تنها کافیست مقدار ماکزیمیم بین کزییم قبلی و عنصر جدید را محاسبه کنیم.
بنابر این برای حذف کارهای تکراری در حلقه دورنی باید الگوریتم را بگونه ای تغییر دهیم که بجای حذف عناصر و بروزرسانی ماکزیمم، شامل افزودن یک عنصر و محاسبه ماکزیمم (یا مینیمم) باشد. برای این کار می توانیم الگوریتم را به این صورت عوض کنیم: از ابتدای لیست هر بار یک روز D را به عنوان روز فروش انتخاب می کنیم و بین روزهای گذشته آن مینیمم قیمت سهام را بدست می آوریم (ارایه راه حل بهتر). این حالت خرید-فروش پرسود ترین معامله ممکن است اگر که فروش در روز D انجام شود.
به عنوان مثال با نگاهی به نمودار قیمت ها می فهمیم که اگر بخواهیم روز چهارم سهم را بفروشیم بهترین زمان برای خرید روز سوم است که قیمت هر سهم (8) کمترین قیمت سهم در روزهای گذشته است. محاسبه برای روز بعد راحت است زیرا اگر بخواهیم در روز پنجم سهم را بفروشیم لزومی ندارد که همه روزهای قبل را برای پیدا کردن مقدار کمینه بپیماییم. بلکه باید مینیمم بین 8 (مینیمم کنونی) و قیمت سهام در روز چهارم (17) را بیابیم. بنابراین نیازی به پیمایش دوباره کل عناصر لیست از ابتدا تا روز پنجم را نیست.
پس کافیست با در نظر گرفتن هر روز به عنوان روز فروش، مینیمم قیمت سهام در روزهای گذشته را بدانیم تا بتوانیم بیشینه سود ممکن را محاسبه کنیم. اگر این میزان را برای هر یک از روز های محاسبه نماییم آنگاه مقدار بیشینه بین این مقادیر جواب مورد نظر خواهد بود. در مصاحبه یک دور کامل این الگوریتم را روی داده ورودی تست می کنیم تا مطمین شویم که الگوریتم درست است (الگوریتم جدید).
برای تحلیل سرانگشتی پیچیدگی محاسباتی این الگوریتم می توانیم به این نکته توجه کنیم که الگوریتم ما یک حلقه دارد که به تعداد روزهایی که قیمت سهام را داریم تکرار می شود. برای هر تکرار، باید مینیمم قیمت در روزهای قبلی را بیابیم. برای این کار کافی است که مینیمم کنونی را با قیمت سهام در روز گذشته مینیمم بگیریم. هزینه انجام این کار ثابت است (با نماد (O(1 نشان داده می شود) و بستگی به تعداد عناصر لیست ندارد. بنابراین اگر طول این لیست n باشد، پیچیدگی محاسباتی این الگوریتم (O(n می باشد.
سپس شروع به نوشتن برنامه می کنیم. تابعی با نام مناسب و یک پارامتر از نوع لیست تعریف می کنیم (خط 2). یک متغیر به نام pmin برای نگهداری کمترین قیمت سهام با مقدار اولیه بینهایت (بعبارت دقیقتر بزرگترین مقدار صحیح در پایتون) در نظر میگیریم (خط 3). یک متغیر دیگر به نام profit برای نگهداری بیشینه سود با مقدار اولیه صفر در نظر میگیریم (خط 4). سپس با استفاده از یک حلقه تکرار در هر تکرار میزان مینیمم کنونی را بروز می کنیم. برای این کار مینیمم بین مقدار جدید و مینیمم کنونی را محاسبه میکنیم (خط 7). آنگاه سود حاصل خرید یک سهم در روز i ام را با فرض خرید با قیمت کمینه در روزهای گذشته محاسبه می نماییم. این مقدار بیشینه سود در صورتی که سهم را در روز iام بفروشیم بدست می آید. بیشینه این مقدار را با بیشینه سود ممکن در روزهای گذشته محاسبه می کنیم و به عنوان میزان بیشینه سود در نظر میگیریم (خط 9). پس از اتمام حلقه تکرار میزان بیشینه سود ممکن را برمی گردانیم (خط 10). تکه کد زیر پیاده سازی الگوریتم بهینه را نشان می دهد.
در یک مصاحبه واقعی میزان برنامه رو پس از نوشتن یکبار دیگر مرور می کنیم و با داده های ورودی تست می کنیم که مطمین شویم که درست کار می کند.
