problem：
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.
Array Dynamic Programmingthinking：
（1）其实就是求一个数组元素两个元素之间的最大差值，使用后面的数减去前面的数
（2）典型的 DP思路，开一个N大小的数组，记录该位置的减去前面最小元素的差值，
最后找出差值数组的最大值即可，时间复杂度O（N）
code：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
if(n==0)
return 0;
vector<int> f(n,0);
int minprice=prices[0];
for(int i=0;i<n;i++)
{
minprice=min(minprice,prices[i]);
f[i]=prices[i]-minprice;
}
int profit=f[0];
for(int j=0;j<n;j++)
profit=max(profit,f[j]);
return profit;
}
};leetcode || 121、Best Time to Buy and Sell Stock
原文：http://blog.csdn.net/hustyangju/article/details/45306207