题目描述:
假设你有一个数组，其中第i个元素是第i天给定股票的价格。
如果你只被允许完成最多一笔交易(即买入并卖出一股股票)，请设计一个算法来查找最大利润。
- 请注意，在购买之前不能出售股票
Example1
Input: [7,1,5,3,6,4]
Output: 5
Explanation
第二天买入，第五天卖出，利润是6-1=5.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation
在这个例子中，没有交易做成因为最大利润是零
C++输入格式
class Solution {
public:
int maxProfit(vector<int>& prices) {
}
};
范例一
子函数
class Solution {
public:
int maxProfit(vector<int> &prices)
{
int maxPro = 0;
int minPrice = INT_MAX;//整型上限
for(int i = 0; i < prices.size(); i++)
{
minPrice = min(minPrice, prices[i]);
cout<<minPrice<<" ";
maxPro = max(maxPro, prices[i] - minPrice);
cout<<maxPro<<endl;
}
return maxPro;
}
};
main()
int main()
{
vector<int> vec;
int i=0;
int m =0;
int a[10]={7,1,5,3,6,4};
for(i=0;i<6;i++)
{
vec.push_back(a[i]);
}
vector<int>::iterator pos;
//声明一个迭代器，来访问vector容器。作用:遍历或指向vector容器的元素
cout<<"输入数组:";
for(pos = vec.begin();pos!=vec.end();pos++)
{
cout<<*pos<<" ";
}
cout<<endl;
Solution sol;
m = sol.maxProfit(vec);
cout<<m<<endl;
return 0;
}
测试结果
测试一
测试二
算法思想
第一步:找到第0天到第i天的最低股价
第二步:找到第0天到第i天可以获得的最大利润
也可以先判断prices[i] 和prices[i - 1]的大小再根据该值选择是找最大利润还是最低股价。
如果prices[i] 大于prices[i - 1]，则最大利润可以刷新，否则最低股价可以刷新。
if(prices[i] > prices[i - 1])
{
maxPro = max(maxPro, prices[i] - minPrice);
}else{
minPrice = min(minPrice, prices[i]);
}
另一种方式是判断prices[i] 和prices[i - 1]作减法，若值小于零则置为零否则置为最大值。并且这种方式时间较短
ret += prices[i] - prices[i-1];
cout<<prices[i]<<" ";
cout<<ret<<" "<<endl;
if(ret < 0) ret = 0;
if(ret > max) max = ret;
测试三
