原題
LintCode 149. Best Time to Buy and Sell Stock
Description
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 (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example
Given array [3,2,3,1,2], return 1.
解題
給出股票價(jià)格的變化燎悍，只能交易一次，求利潤最大值盼理。
直接維護(hù)一個(gè)當(dāng)前的最低價(jià)和當(dāng)前的最高利潤谈山，遍歷一次數(shù)組即可。
代碼
class Solution {
public:
/*
* @param prices: Given an integer array
* @return: Maximum profit
*/
int maxProfit(vector<int> &prices) {
// write your code here
int ans = 0;
int minPrice = INT_MAX;
if (prices.empty()) return ans;
for (auto i : prices) {
minPrice = min(minPrice, i);
ans = max(i - minPrice, ans);
}
return ans;
}
};
