กำไรสูงสุดหลังจากซื้อและขายหุ้นใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ stkprice[] ซึ่งระบุราคาของหุ้นที่แน่นอนในวันที่ i-th งานของเราคือสร้างโปรแกรมคำนวณกำไรสูงสุดหลังจากซื้อและขายหุ้นใน C++

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

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

stkprice[] = {120, 310, 405, 210, 150, 550}

ผลลัพธ์

685

คำอธิบาย

ซื้อวันที่ 1 ขายวันที่ 3 จะได้กำไร 285

หลังจากนี้ ซื้อวันที่ 5 ขายวันที่ 6 จะได้กำไร 400

ทำให้มีกำไรรวม (400 + 285) =685

แนวทางการแก้ปัญหา

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

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#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 "<<MaximizeProfit(stkPrice, 0, days);
   return 0;
}

ผลลัพธ์

The Maximum profit is 4196007

วิธีแก้ปัญหาที่มีประสิทธิภาพมากขึ้นนั้นขึ้นอยู่กับการหากำไรสูงสุดจากพวกเขาโดยการหากำไรสูงสุดสำหรับการซื้อขายแต่ละครั้ง สามารถทำได้โดยค้นหาค่าต่ำสุดและค่าสูงสุดของวันซื้อขาย ค่าต่ำสุดในท้องถิ่นคือวันที่ราคาหุ้นต่ำกว่าวันก่อนหน้าและวันถัดไป Andmaxima อยู่ตรงข้ามกับมินิมา หากไม่มีค่าต่ำสุดในพื้นที่ (ภายใน index0 ถึง n-2) วันของพวกเขาจะไม่สามารถทำกำไรได้

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

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#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] );
      // For displaying profit for one minima-maxima cycle
      //cout <<"Stock bought on day "<<(minima+ 1 )<<" and Sold
      on day "<<(maxima+1) <<" at a profit of "<<(price[maxima] - price[minima] )<<"\n";
   }
   cout<<"The maximized profit is "<<maxProfit;
}
int main(){
   int stkPrice[] = { 120, 310, 405, 210, 150, 550 };
   int days = 6;
   MaximizeProfit(stkPrice, days);
   return 0;
}

ผลลัพธ์

The maximized profit is 685