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.
Solution: DP, the objective is to find out the maximum interval (prices[i], prices[j]) where i<j.
class Solution {
public:
int maxProfit(vector<int> &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(prices.empty()) return 0;
int maxProfit = 0;
int curMin = prices[0];
for(int i=1; i<prices.size(); ++i){
curMin = min(curMin, prices[i]);
maxProfit = max(maxProfit, prices[i]-curMin);
}
return maxProfit;
}
};
No comments:
Post a Comment