এই সমস্যায় একটি অ্যারে stkprice[] দেওয়া আছে যা i-তম দিনে একটি স্টকের দাম নির্দেশ করে। আমাদের C++-এ স্টক কিনে ও বিক্রি করে সর্বোচ্চ লাভ বের করার প্রোগ্রাম লিখতে হবে।
সমস্যার বিবরণ - কম দামে কিনে বেশি দামে বিক্রি করে লাভ করা হবে। দাম কমলে আবার কিনে বেড়লে বিক্রি করব। এই চক্র পুনরাবৃত্তি হবে।
উদাহরণ:
ইনপুট
stkprice[] = {120, 310, 405, 210, 150, 550}আউটপুট
685
ব্যাখ্যা
১ম দিন কিনে ৩য় দিন বিক্রি: লাভ ২৮৫। ৫ম দিন কিনে ৬ষ্ঠ দিন বিক্রি: লাভ ৪০০। মোট লাভ = ৬৮৫।
সমাধানের পদ্ধতি
স্থানীয় ন্যূনতম (local minima) এবং স্থানীয় সর্বোচ্চ (local maxima) খুঁজে বের করুন। ন্যূনতমে কিনে পরবর্তী সর্বোচ্চে বিক্রি করুন। সব ন্যূনতম-সর্বোচ্চ জোড়ার লাভ যোগ করলে সর্বোচ্চ লাভ পাওয়া যাবে।
উদাহরণ (রিকার্শিভ - কম কার্যকর)
#include <iostream>
using namespace std;
int max(int a, int b){
if(a > b) return a;
return b;
}
int MaximizeProfit(int stkPrice[], int firstDay, int lastDay){
if (lastDay <= firstDay) return 0;
int maxProfit = 0;
for (int i = firstDay; i < lastDay; i++) {
for (int j = i + 1; j <= lastDay; j++) {
if (stkPrice[j] > stkPrice[i]) {
int profit = ( stkPrice[j] - stkPrice[i] ) + MaximizeProfit(stkPrice, firstDay, i - 1) + MaximizeProfit(stkPrice, j + 1, lastDay);
maxProfit = max(maxProfit, profit);
}
}
}
return maxProfit;
}
int main(){
int stkPrice[] = { 120, 310, 405, 210, 150, 550 };
int days = 6 ;
cout<<"The Maximum profit is "<আউটপুট
The Maximum profit is 4196007
কার্যকর পদ্ধতি (স্থানীয় ন্যূনতম/সর্বোচ্চ)
উদাহরণ
#include <iostream>
using namespace std;
void MaximizeProfit(int price[], int n){
if (n == 1) return;
int maxProfit = 0;
int i = 0;
while (i <= n - 1) {
while ((i <= n - 2) && (price[i + 1] <= price[i])) i++;
int minima = i++;
while ((i < n) && (price[i] >= price[i - 1])) i++;
int maxima = i - 1;
maxProfit += (price[maxima] - price[minima] );
}
cout<<"The maximized profit is "<আউটপুট
The maximized profit is 685
