数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究最多两次买卖一只股票实现利润最大化
交易中，一个买家上午买入股票，下午卖出股票。如果一天最多允许进行两次交易。第二次交易只能在第一次交易完成后进行。如果给定股票价格，则找出买家可以赚取的最大利润。
输入和输出
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
更新于: 2020 年 6 月 17 日
页面浏览量：376
广告