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.
简单的动态编程问题，可是一开始我没读懂题目的意思。这里的买入当然应该在卖出之前，所以说不是那种取一个max一个min相减就能解决的，代码如下：
1 class Solution { 2 public: 3 int maxProfit(vector<int>& prices) { 4 int sz = prices.size(); 5 if(sz == 0 || sz == 1) return 0; 6 int min, maxGain; 7 min = prices[0];//min的初值要注意 8 maxGain = 0; 9 for(int i = 0 ; i < sz; ++i){ 10 if(min > prices[i]) 11 min = prices[i]; 12 else if(maxGain < prices[i] - min) 13 maxGain = prices[i] - min; 14 } 15 return maxGain; 16 } 17 };
LeetCode OJ：Best Time to Buy and Sell Stock（股票买卖的最佳时期）
原文：http://www.cnblogs.com/-wang-cheng/p/4878996.html