กำไรสูงสุดโดยการซื้อและขายหุ้นสูงสุดสองครั้ง

ในการซื้อขาย ผู้ซื้อรายหนึ่งซื้อและขายหุ้นในตอนเช้าและตอนเย็นตามลำดับ หากอนุญาตให้ทำธุรกรรมได้ไม่เกินสองรายการในหนึ่งวัน ธุรกรรมที่สองสามารถเริ่มต้นได้หลังจากธุรกรรมแรกเสร็จสิ้นเท่านั้น หากกำหนดราคาหุ้น ให้หากำไรสูงสุดที่ผู้ซื้อสามารถทำได้

อินพุตและเอาต์พุต

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