R e l a t a b l e C o d e

جاوا اسکریپت LeetCode بهترین زمان برای خرید و فروش سهام

16 مه 2022 • 4 دقیقه خواندن

سریع

قیمت های آرایه ای به شما داده می شود که قیمت ها[i] قیمت یک سهم معین در روز پنجم است.

شما می خواهید با انتخاب یک روز برای خرید یک سهم و انتخاب روز متفاوت در آینده برای فروش آن سهام، سود خود را به حداکثر برسانید.

حداکثر سودی که می توانید از این معامله به دست آورید را برگردانید. اگر نمی توانید به هیچ سودی برسید، 0 برگردانید.

مثال 1:

ورودی: قیمت ها = [7،1،5،3،6،4] خروجی: 5 توضیح: در روز 2 بخرید (قیمت = 1) و در روز 5 بفروشید (قیمت = 6)، سود = 6-1 = 5. توجه داشته باشید که خرید در روز دوم و فروش در روز اول ممنوع است زیرا قبل از فروش باید خرید کنید. تجزیه و تحلیل مشکل

همانند مشکلات قبلی، اولین راه حل ظاهری این است که به سراغ راه حل brute force بروید. در اینجا ما دو بار روی آرایه تکرار می کنیم و هر تفریق بین هر مقدار بعدی را بررسی می کنیم و فقط بالاترین سود را می گیریم.

یک مثال بصری از این می تواند به شکل زیر باشد:

راه حل اول

بیایید جلو برویم و کد آنچه در بالا ذکر کردیم بنویسیم.

تابع حداکثر سود( قیمت) <اجازه دهیدسود =0; برای ( اجازه دهیدمن =0; منطول - 1; من ++)<برای ( اجازه دهیدj = i +1; jطول; j++)<پایانCurrentProfit = قیمت ها[j] - قیمت ها[i];if (currentProfit>سود)>> برگشت profit;>

در اینجا قیمت عنصر بعدی در آرایه را با جریان مقایسه می کنیم. بهترین راه برای مفهوم سازی این است که i شاخص ما است و j نشانگر ما است که به تکرار ادامه می دهد.

برای یافتن حداکثر سود از دو حلقه for استفاده می کنیم. این پیچیدگی O(n^2) خواهد داشت. این یک مشکل بسیار بزرگ است زیرا بسیار کند است! با این حال، ما می توانیم این را تنها با یک بار تکرار روی آرایه بهینه کنیم.

راه حل دوم

اما یک تکرار واحد چگونه خواهد بود؟

با کد چیزی شبیه به این خواهد بود:

varحداکثر سود =تابع ( قیمت) <اجازه دهیدسود =0; اجازه دهیدسهام برای خرید = قیمت ها[0]; برای ( اجازه دهیدمن =1; منطول; من ++)<if (stockToBuy>قیمت ها[i])پایانCurrentProfit = قیمت ها[i] - stockToBuy;if (currentProfit>سود)> برگشت profit;>;

ما سهام ToBuy اولیه را از اولین عنصر آرایه می گیریم. سپس می توانیم تکرار را روی آرایه شروع کنیم (اول را رد کنیم). اگر سهام بعدی قیمتی بالاتر از سهام انتخابی فعلی ما داشته باشد، مقایسه می کنیم. اگر چنین است، سود بیشتری برای ما به همراه خواهد داشت، بنابراین آن را حذف می کنیم.

با این حال، این همچنین به عنوان یک مکانیسم تنظیم مجدد عمل می کند. اگر سهام دارای ارزش بالاتری باشد، می دانیم که از این نقطه به بعد سود بیشتری نسبت به سهام انتخاب شده قبلی نخواهد داشت.

stockToBuy = قیمت ها[i];

پس از آن، سود جاری جدید خود را محاسبه می کنیم، این فقط یک مقدار موقت در تکرار فعلی ما است.

پایانCurrentProfit = قیمت ها[i] - stockToBuy;

سپس آن را با مقداری که خارج از حلقه for خود ذخیره کرده ایم مقایسه می کنیم. اگر بالاتر باشد، دقیقاً همان چیزی است که ما می خواهیم.

توجه داشته باشید که ابتدا متغیر را با 0 ایجاد کردیم تا اگر سودی پیدا نکردیم بتوانیم آن را همانطور که هست برگردانیم.

الگوریتم حریص

اما این اسمش چیه؟

کاری که ما در اینجا انجام می دهیم این است که در هر تکرار بهترین گزینه را انتخاب می کنیم و انتخاب های گذشته را فراموش می کنیم به این الگوریتم حریص گفته می شود.

در اینجا یک مقاله ویکی پدیا آمده است اگر می خواهید در مورد آن بیشتر بخوانید (باید).

بیایید وصل شویم

اگر دوست داشتید از طریق لینکدین یا توییتر با من در ارتباط باشید

نقشه راه توسعه دهنده رایگان من و اخبار هفتگی صنعت فناوری را در خبرنامه من بررسی کنید.

در صورت مشاهده هرگونه اشتباه تایپی یا اشتباه می توانید مقاله را مستقیماً در GitHub ویرایش کنید

در صدر صنعت فناوری بمانید و به عنوان یک توسعه دهنده با مجموعه ای از مقالات و اخبار در کنار مشاوره، مشاهدات و بینش شخصی، رشد کنید. ویدیو های آموزشی فارکس...