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

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

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

مثال 1:

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

مثال 2:

ورودی: قیمت ها = [7،6،4،3،1]خروجی: 0توضیح: در این حالت هیچ معامله ای انجام نمی شود و حداکثر سود = 0 است.

دو راه حل

Leetcode راه حل هایی را برای چالش های آن ها ارائه می کند و می توان آن ها را حلقه زد و رویکردهای مختلف را یاد گرفت.

برای این سوال Leetcode 2 راه حل ممکن ارائه کرده است:

1. به اصطلاح راه حل Brute Force، که تمام ترکیبات ممکن را بررسی می کند و حداکثر سود را پیدا می کند.
2. رویکرد One Pass - جایی که به جای بررسی هر ترکیب ممکن، به دنبال مقادیر حداقل و حداکثر می گردیم.

نیروی بی رحم

ما با اعلام متغیر maxProfit خود شروع می کنیم و آن را 0 می کنیم.

اجازه دهید maxProfit = 0;

برای بررسی هر ترکیب ممکن، دو بار در آرایه تکرار می کنیم. اولین تکرار انتخاب قیمت خرید ما خواهد بود (من آن را buyPrice نامیدم) و تکرار دوم به دنبال sellPrice خواهد بود.

برای (بگذارید i = 0؛ iاجازه خرید قیمت = قیمت ها[i];. >

اولین حلقه for از تمام عناصر آرایه i به جز آخرین عنصر عبور می کند

برای (j = i+1؛ jlet sellPrice = قیمت ها[j];. >

حلقه دوم از موقعیت i+1 شروع می شود، زیرا همان عنصر نمی تواند همزمان قیمت خرید و فروش باشد و در داخل حلقه اول قرار می گیرد.

if (sellPrice>خرید قیمت)<اجازه دهید سود = فروش قیمت — خرید قیمت;. >

اکنون بررسی خواهیم کرد که آیا فروش حتی منطقی است (اگر sellPrice بالاتر از buyPrice باشد) و اگر انجام داد می توانیم سود را محاسبه کنیم.

if (profit>حداکثر سود)<maxProfit = سود;>

آخرین مرحله این است که بررسی کنید آیا سود در عناصر فعلی بالاتر از maxProfit است و maxProfit را به روز می کند.

کد (2 حلقه)

Leetcode نمودار فوق را ارائه می دهد و مشخص می کند که ما واقعاً باید به دنبال حداقل قیمت باشیم که مطابق با قیمت خرید و حداکثر قیمت است که بالاترین بازده را به همراه خواهد داشت.

اجازه دهید maxProfit = 0;اجازه دهید minPrice = Number. MAX_VALUE;

بنابراین ما 2 متغیر را تنظیم خواهیم کرد ، MaxProfit همان روشی که ما آن را در رویکرد نیروی بی رحمانه و مینی نسخه با استفاده از شماره. max_value انجام دادیم زیرا باید با بالاترین تعداد ممکن در اینجا شروع کنیم.

برای (بگذارید i = 0؛ i. >

حلقه ما از طریق هر عنصر از آرایه قیمت ها تکرار می شود.

if (minPrice>قیمت ها [i]) minprice = قیمت [i] ؛>

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

else if (prices[i] - minPrice>maxprofit) maxprofit = قیمت [i] - minprice ؛>

در صورت پایین بودن MinPrice ، می توانیم بررسی کنیم که آیا سود ما بالاتر از مقدار حداکثر است و بر این اساس آن را به روز می کند. پس از تکرار کل آرایه ، در نهایت حداقل قیمت و حداکثر سود را پیدا خواهیم کرد.

MaxProfit را برگردانید ؛

اوه ، بله ، و لطفا فراموش نکنید که نتیجه خود را برگردانید!< Pan> بنابراین ما 2 متغیر را تنظیم خواهیم کرد ، حداکثر ، همان روشی که ما آن را در رویکرد نیروی بی رحمانه و minprice با استفاده از number. max_value انجام دادیم زیرا باید با بالاترین تعداد ممکن در اینجا شروع کنیم.