Trong giao dịch, một người mua mua và bán cổ phiếu lần lượt vào buổi sáng và buổi tối. Nếu tối đa hai giao dịch được phép trong một ngày. Giao dịch thứ hai chỉ có thể bắt đầu sau khi giao dịch đầu tiên hoàn thành. Nếu giá cổ phiếu được đưa ra, thì hãy tìm lợi nhuận tối đa mà người mua có thể kiếm được.
Đầu vào và Đầu ra
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
Thuật toán
findMaxProfit(pricelist, n)
Đầu vào - Danh sách tất cả các giá, số lượng mặt hàng trong danh sách.
Đầu ra - Lợi nhuận tối đa.
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
Ví dụ
#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); }
Đầu ra
Maximum Profit = 100