শেয়ার কেনা-বেচে সর্বোচ্চ লাভ (সর্বোচ্চ দুবার ট্রানজ্যাকশন)

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

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

ইনপুট: শেয়ার দামের তালিকা।
{2, 30, 15, 10, 8, 25, 80}

আউটপুট: এখানে মোট লাভ ১০০।
২ দামে কিনে ৩০ দামে বিক্রি। লাভ ২৮।
তারপর ৮ দামে কিনে আবার ৮০ দামে বিক্রি। লাভ ৭২।
মোট লাভ ২৮ + ৭২ = ১০০

অ্যালগরিদম

findMaxProfit(pricelist, n)

ইনপুট: সকল দামের তালিকা, তালিকায় আইটেম সংখ্যা।
আউটপুট: সর্বোচ্চ লাভ।

শুরু
  n আকারের profit অ্যারে সংজ্ঞায়িত করুন এবং ০ দিয়ে পূরণ করুন
  maxPrice := pricelist[n-1]  // শেষ আইটেম নির্বাচন
  i := n-2 থেকে 0 পর্যন্ত নিচের দিকে, করুন
    যদি pricelist[i] > maxPrice হয়, তবে
      maxPrice := pricelist[i]
    profit[i] := profit[i+1] এবং (maxPrice - pricelist[i]) এর মধ্যে সর্বোচ্চ
  শেষ
  minPrice := pricelist[0]  // প্রথম আইটেম নির্বাচন
  i := 1 থেকে n-1 পর্যন্ত, করুন
    যদি pricelist[i] < minPrice হয়, তবে
      minPrice := pricelist[i]
    profit[i] := profit[i-1] এবং (profit[i] + (pricelist[i] - minPrice)) এর মধ্যে সর্বোচ্চ
  শেষ
  profit[n-1] ফেরত দিন
শেষ

উদাহরণ (C++)

#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=0; i--) {
    if (priceList[i] > maxPrice)
      maxPrice = priceList[i];
    profit[i] = max(profit[i+1], maxPrice - priceList[i]);
  }

  int minPrice = priceList[0];
  for (int i=1; i