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

ปัญหา

ในปัญหานี้ เราได้รับอาร์เรย์ stkprice[] ที่แทนราคาของหุ้นชนิดหนึ่งในวันที่ i งานของเราคือสร้างโปรแกรมเพื่อคำนวณกำไรสูงสุดหลังจากซื้อและขายหุ้นใน 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

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

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

ตัวอย่างโค้ด (วิธีที่ดีกว่า)

#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