股票买卖是面试当中另外一个常见的问题。问题的描述是：给出一个数组，数组中的的数表示每个时刻股票的价格。如果只允许买卖一次，请写出一个算法给出可能的最大收益。基础的算法是对于一个个时刻，搜索其能得到的最大收益，最后在所有的最大收益当中选择一个最大值输出。这样的算法复杂度为O（n^2）。一个比较好的算法是，使用两个变量一个记录当前遇到的最低股价，一个计算当前的最大收益。从左到右搜索数组，如果当前价格与最低股价的差大于最大收益，则将当前最大收益保存下来。扫描结束后，便可得到最大的收益。该题目在leetcode的OJ上面有，下面是该算法的Java实现。
public class Solution {
/**
* 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.
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] A = {2,1,4};
System.out.print(new Solution().maxProfit(A));
}
public int maxProfit(int[] prices) {
// Start typing your Java solution below
// DO NOT write main() function
if(prices == null || prices.length == 0)
return 0;
int maxprofit = 0;
int lowest_before = Integer.MAX_VALUE;
for(int i = 0; i < prices.length; i++){
if(lowest_before > prices[i])
lowest_before = prices[i];
else if(prices[i] - lowest_before > maxprofit){
maxprofit = prices[i] - lowest_before;
}
}
return maxprofit;
}
}