大家好，又见面了，我是全栈君。
1.买卖股票的最佳时机
假设你有一个数组，其中第 i 个元素是一支给定股票第 i 天的价格。如果您只能完成最多一笔交易（即买入和卖出一股股票），则设计一个算法来找到最大的利润。
输入: [7, 1, 5, 3, 6, 4]
输出: 5
最大利润 = 6-1 = 5（不是 7-1 = 6, 因为卖出价格需要大于买入价格）分析:
1.只能交易一笔
2.变量current为买入价格，max为最大利润
3.低则买入，高则卖出
int maxProfit(vector<int>& prices) {
if(prices.empty())return 0;
int max=0,current=prices[0];
for(int i=1;i<prices.size();i++){
if(current>prices[i]){
current=prices[i];
}else{
int sum=prices[i]-current;
if(sum>max)max=sum;
}
}
return max;
}2.买卖股票的最佳时机 II
假设有一个数组，它的第 i 个元素是一个给定的股票在第 i 天的价格。设计一个算法来找到最大的利润。你可以完成尽可能多的交易（多次买卖股票）。然而，你不能同时参与多个交易（你必须在再次购买前出售股票）。
分析:
1.可以交易多笔
2.相邻价格中，只要后一次比前一次高，就买入
int maxProfit(vector<int>& prices) {
if(prices.empty())return 0;
int max = 0;
for(int i=1; i<prices.size(); i++) {
if(prices[i] - prices[i-1] > 0) {
max += (prices[i] - prices[i-1]);
}
}
return max;
}3.买卖股票的最佳时机 III
假设你有一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来找到最大的利润。你最多可以完成两笔交易。你不可同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
分析:
1.最多可以进行两笔交易
2.将数组分为左右两个子数组，分别求出对应的最大利润
int maxProfit(vector<int>& prices) {
if(prices.empty())return 0;
int min=prices.front(),max=prices.back(),size=prices.size();
vector<int> left(size,0);
vector<int> right(size,0);
for(int i=1;i<size;i++){
if(prices[i]>min){
left[i]=(prices[i]-min)>left[i-1]?(prices[i]-min):left[i-1];
}else{
left[i]=left[i-1];
min=prices[i];
}
}
for(int i=size-2;i>=0;i--){
if(prices[i]<max){
right[i]=(max-prices[i])>right[i+1]?(max-prices[i]):right[i+1];
}else{
right[i]=right[i+1];
max=prices[i];
}
}
int result=0;
for(int i=0;i<size;i++){
result=(right[i]+left[i])>result?(right[i]+left[i]):result;
}
return result;
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/107604.html原文链接：https://javaforall.net
