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

وقتی صحبت از حل مسئله الگوریتمی می شود ، یکی از چالش های کلاسیک که توسعه دهندگان با آن روبرو می شوند ، مشکل “بهترین زمان برای خرید و فروش سهام” است. این مشکل یک تمرین عالی در بهینه سازی حداکثر سود در حالی که به محدودیت های خاص پایبند است. در این پست وبلاگ ، ما به یک راه حل زیبا و کارآمد که در جاوا نوشته شده است ، کشف خواهیم کرد ، چگونه کار می کند و منطق آن را گام به گام تجزیه می کنیم.

بیانیه مشکل

مشکل ساده و در عین حال جذاب است: به شما یک آرایه داده می شود prices، کجا prices[i] قیمت سهام در iروز هفتم هدف شما این است که با انتخاب یک روز واحد برای خرید سهام و یک روز متفاوت در آینده برای فروش آن ، سود خود را به حداکثر برسانید. گرفتن؟ شما فقط می توانید یک معامله را انجام دهید (یعنی یک خرید و به دنبال آن یک فروش) ، و در صورت عدم وجود سود حاصل ، شما 0 را برمی گردانید.

در اینجا جزئیات کلیدی وجود دارد:

• ورودی: مجموعه ای از اعداد صحیح prices نمایندگی قیمت سهام روزانه.
• خروجی: حداکثر سود قابل دستیابی ، یا 0 در صورت عدم امکان سود.
• محدودیت ها:
  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^4

نمونه

1. ورودی: prices = [7, 1, 5, 3, 6, 4]

   خروجی: 5

   توضیح: در روز 2 (قیمت = 1) بخرید و در روز 5 (قیمت = 6) بفروشید. سود = 6 – 1 = 5.

2. ورودی: prices = [7, 6, 4, 3, 1]

   خروجی: 0

   توضیح: قیمت ها فقط کاهش می یابد ، بنابراین هیچ سود حاصل نمی شود.

راه حل

در اینجا کد جاوا وجود دارد که این مشکل را به طور کارآمد حل می کند:

import static java.lang.Math.*;

class Solution {
    public int maxProfit(int[] prices) {        
        int profit = 0;
        int buy = 10_001; // A value larger than the max possible price
        for (int i = 0; i < prices.length; i++) {
            profit = max(prices[i] - buy, profit);
            buy = min(prices[i], buy);
        }
        return profit;
    }
}

این راه حل مختصر است ، اجرا می شود o (n) زمان (کجا n طول آن است prices آرایه) ، و استفاده می کند o (1) فضای اضافی بیایید آن را تجزیه کنیم.

چگونه کار می کند

بینش کلیدی

این مشکل حداکثر سود را از یک معامله خرید و فروش واحد درخواست می کند. این بدان معنی است که ما باید حداکثر تفاوت بین دو عنصر را در آرایه پیدا کنیم ، جایی که عنصر کوچکتر (قیمت خرید) قبل از عنصر بزرگتر (قیمت فروش) می آید. به جای بررسی هر جفت احتمالی روز خرید و فروش (که زمان O (n²) را می طلبد) ، می توانیم با ردیابی حداقل قیمت دیده شده تاکنون و محاسبه سود بالقوه در هر مرحله ، این امر را بهینه کنیم.

توضیح گام به گام

1. متغیرها را اولیه کنید:

   • profit: از 0 شروع می شود و حداکثر سود موجود در تاکنون را نشان می دهد.
   • buy: اولیه به 10_001، مقداری بیشتر از حداکثر قیمت ممکن (10^4). این تضمین می کند که قیمت اول در آرایه آن را به روز می کند.

2. از طریق آرایه تکرار کنید:

   • برای هر روز i، ما:
     • سود بالقوه را در صورت فروش محاسبه کنید prices[i] بعد از خرید با کمترین قیمت که تاکنون دیده شده است (buy). این کار با max(prices[i] - buy, profit)بشر
     • بروزرسانی buy حداقل قیمت فعلی prices[i] و قبلی buy ارزش ، اطمینان حاصل می کنیم که ما همیشه کمترین قیمت را تا این مرحله با آن روبرو هستیم.

3. نتیجه را برگردانید:

   • بعد از حلقه ، profit حداکثر سود قابل دستیابی را در اختیار دارد.

به عنوان مثال پیاده روی

بیایید نمونه اول را اجرا کنیم: prices = [7, 1, 5, 3, 6, 4]بشر

بعد از حلقه ، profit = 5، که با خروجی مورد انتظار مطابقت دارد.

چرا کار می کند

• صحت: این الگوریتم تضمین می کند که برای هر قیمت فروش ، ما کمترین قیمت خرید را که قبل از آن دیده می شود ، کم می کنیم و قانون “خرید قبل از فروش” را برآورده می کنیم.
• کارایی: فقط به یک پاس واحد از طریق آرایه (O (N) زمان) نیاز دارد و از دو متغیر (O (1) فضا) استفاده می کند.
• لبه های لبه: مواردی را در اختیار شما قرار می دهد که هیچ سودی امکان پذیر نیست (به عنوان مثال ، کاهش قیمت) با نگه داشتن profit در 0 هنگامی که اختلافات منفی رخ می دهد.

پیچیدگی زمان و فضا

• پیچیدگی زمانی: o (n) ، کجا n طول آن است prices آرایه ما فقط یک بار آرایه را طی می کنیم.
• پیچیدگی فضا: o (1) ، زیرا ما فقط از دو متغیر استفاده می کنیم (profit وت buy) صرف نظر از اندازه ورودی.

پایان

مشکل “بهترین زمان برای خرید و فروش سهام” نمونه ای خارق العاده از چگونگی تقسیم یک کار به ظاهر پیچیده در یک الگوریتم ساده و کارآمد با رویکرد درست است. با ردیابی حداقل قیمت و به روزرسانی حداکثر سود در یک پاس ، این راه حل از مقایسه های غیر ضروری جلوگیری می کند و عملکرد بهینه را ارائه می دهد.

این که آیا شما در حال آماده سازی برای برنامه نویسی مصاحبه هستید یا فقط مهارت های حل مسئله خود را تیز می کنید ، این مشکل و راه حل آن ارزش افزودن به ابزار شما را دارد. آن را با موارد تست مختلف امتحان کنید و ببینید که چقدر ظریف محدودیت ها را کنترل می کند!

برنامه نویسی مبارک!