By

文章目录
  1. 1. 问题
  2. 2. 解析
  3. 3. 代码
  4. 4. 参考

问题

一个人知道未来n天的每天股票的价格，请你给出一个算法，使得这个人从哪天买入，哪天卖出能获得最大的收益。

解析

问题实际上就是求一个数组后面元素减前面元素的最大值
看了大神们提出了一个O(n)的方法，就是遍历过去，同时记录当前最小的那个元素，然后每次都是当前遍历元素减去最小的元素 取其差值最大

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 通过维护一个最小的minLeft  来计算最大的差值  聪明
 * @param a
 * @return
 */
public static int stock(int[] a)
{
	if(a.length<2)
	{
		//都来不及买和卖  肯定不做了
		return 0;
	}
	
	int max=a[1]-a[0];
	int minLeft=a[0];
	
	for(int i=2;i<a.length;i++)
	{
		minLeft=Math.min(minLeft, a[i-1]);//通过最小的价格买下
		max=Math.max(max, a[i]-minLeft);//计算买了能赚最大的钱
	}
	
	return Math.max(0, max);//再怎么也不能亏
}

测试

1
2
3
4
public static void main(String[] args) {
	int[] a={4, 4, 2, 14, 1, 2, 15};
	System.out.println(stock(a));
}

14

其他两个股票升级问题看

参考

http://www.cnblogs.com/iamccme/archive/2013/05/21/3091706.html

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

文章目录
  1. 1. 问题
  2. 2. 解析
  3. 3. 代码
  4. 4. 参考