码农乌托邦

楠哥小站

楠哥,理想主义码农,就职于Google,现居纽约。


Best Time to Buy and Sell Stock

股票买卖是面试当中另外一个常见的问题。问题的描述是:给出一个数组,数组中的的数表示每个时刻股票的价格。如果只允许买卖一次,请写出一个算法给出可能的最大收益。基础的算法是对于一个个时刻,搜索其能得到的最大收益,最后在所有的最大收益当中选择一个最大值输出。这样的算法复杂度为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;        
    }
}
最近的文章

Leetcode中使用的二叉树结构

在leetcode中使用的二叉树,大多是"双指针"二叉树,即每个节点有指向其两个孩子的两个指针。同时,每个节点都有一个域存储该节点的int型值。每个节点写成一个类,该类每个域都是默…

Technical, Career继续阅读
更早的文章

Two Sum

Two Sum是各种面试题当中的经典题目。题目是给定一个目标和和一个数组,找出和等于目标和的所有数对。题目的解法有很多,比如使用hash map把数组进行hash存储,之后查找每个元素是否可以找到对应…

Technical, Career继续阅读
comments powered by Disqus