সর্বাধিক দুবার একটি শেয়ার ক্রয় এবং বিক্রি করে সর্বাধিক লাভ

একটি ট্রেডিংয়ে, একজন ক্রেতা যথাক্রমে সকাল ও সন্ধ্যায় শেয়ার ক্রয় ও বিক্রয় করেন। যদি দিনে সর্বাধিক দুটি লেনদেনের অনুমতি দেওয়া হয়। প্রথমটি সম্পূর্ণ হওয়ার পরেই দ্বিতীয় লেনদেন শুরু হতে পারে। যদি স্টক মূল্য দেওয়া হয়, তাহলে ক্রেতা সর্বোচ্চ মুনাফা পেতে পারেন।

ইনপুট এবং আউটপুট

Input:
A list of stock prices. {2, 30, 15, 10, 8, 25, 80}
Output:
Here the total profit is 100. As buying at price 2 and selling at price 30.
so profit 28. Then buy at price 8 and sell it again at price 80.
So profit 72. So the total profit 28 + 72 = 100

অ্যালগরিদম

findMaxProfit(pricelist, n)

ইনপুট - সমস্ত দামের তালিকা, তালিকায় আইটেমের সংখ্যা।

আউটপুট - সর্বোচ্চ লাভ।

Begin
   define profit array of size n and fill with 0
   maxPrice := pricelist[n-1]          //last item is chosen

   for i := n-2 down to 0, do
      if pricelist[i] > maxPrice, then
         maxPrice := pricelist[i]
      profit[i] := maximum of profit[i+1] and maxProfit – pricelist[i]
   done

   minProce := pricelist[0]           //first item is chosen
   for i := 1 to n-1, do
      if pricelist[i] < minPrice, then
         minPrice := pricelist[i]
      profit[i] := maximum of profit[i-1] and (profit[i]+(pricelist[i] - minPrice))
   done

   return profit[n-1]
End

উদাহরণ

#include<iostream>
using namespace std;

int max(int a, int b) {
   return (a>b)?a:b;
}

int findMaxProfit(int priceList[], int n) {
   int *profit = new int[n];
   for (int i=0; i<n; i++)            //initialize profit list with 0
      profit[i] = 0;

   int maxPrice = priceList[n-1];        //initialize with last element of price list

   for (int i=n-2;i>=0;i--) {
      if (priceList[i] > maxPrice)
         maxPrice = priceList[i];

      profit[i] = max(profit[i+1], maxPrice - priceList[i]);     //find the profit for selling in maxPrice
   }

   int minPrice = priceList[0];            //first item of priceList as minimum

   for (int i=1; i<n; i++) {
      if (priceList[i] < minPrice)
         minPrice = priceList[i];

      profit[i] = max(profit[i-1], profit[i] + (priceList[i]- minPrice) );
   }

   int result = profit[n-1];
   return result;
}

int main() {
   int priceList[] = {2, 30, 15, 10, 8, 25, 80};
   int n = 7;
   cout << "Maximum Profit = " << findMaxProfit(priceList, n);
}

আউটপুট

Maximum Profit = 100