कम से कम दो बार शेयर खरीदकर और बेचकर अधिकतम लाभ

एक ट्रेडिंग में, एक खरीदार सुबह शेयर खरीदता है और शाम को बेचता है। यदि एक दिन में अधिकतम दो लेनदेन की अनुमति है। दूसरा लेनदेन तभी शुरू हो सकता है जब पहला पूरा हो जाए। यदि स्टॉक की कीमतें दी गई हैं, तो खरीदार द्वारा कमाया जा सकने वाला अधिकतम लाभ ढूंढें।

इनपुट और आउटपुट

इनपुट: स्टॉक कीमतों की सूची
{2, 30, 15, 10, 8, 25, 80}

आउटपुट: यहां कुल लाभ 100 है।
कीमत 2 पर खरीदकर 30 पर बेचा। लाभ 28।
फिर कीमत 8 पर खरीदकर 80 पर बेचा। लाभ 72।
कुल लाभ 28 + 72 = 100

एल्गोरिदम

findMaxProfit(pricelist, n)

इनपुट: सभी कीमतों की सूची, सूची में आइटम्स की संख्या
आउटपुट: अधिकतम लाभ

शुरुआत
    profit ऐरे को आकार n का परिभाषित करें और 0 से भरें
    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 < n; i++)
        profit[i] = 0;
    
    int maxPrice = priceList[n-1];
    for (int i = n-2; 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 < 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