
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
int maxProfit(vector<int>& prices) {
if(prices.size()<=1) return 0;
int min=prices[0];
int res=0;
for(int i=1;i<prices.size();++i){
if(min>prices[i])min=prices[i];
if(prices[i]-min > res)res=prices[i]-min;
}
return res;
}
从前往后遍历 如果遇到比min小的 对min修改
因为如果后面大的只能对前面小的进行比较 相对于修改前的min,已经没有意义了
发表评论
沙发空缺中,还不快抢~