Desciption

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 (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]

Output: 5

Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]

Output: 0

Explanation: In this case, no transaction is done, i.e. max profit = 0.

思考

最直观的方式是检查所有可能的买卖组合。但是注意卖出一定是在买入之后。假设买入价为 a，卖出价为 b，b-a 需要取一个最大值，既然卖出在后，买入在前，那么数组中的一个元素，不可能同时是 a 和 b ，且 a 一定是位于 b 之前的所有数中最小的那个，因此在一次遍历中，我们对每个元素进行检查，先看它是否是 a（当前最小的数）， 如果不是 a，那么再检查它是否是 b（当前令 b - a 最大的数）。遍历完成后，就可以得到 b - a 的最大值了。

func maxProfit(prices []int) int {	minprice := math.MaxInt64	maxprofit := 0	for _, p := range prices {		if p < minprice {			minprice = p		} else if p-minprice > maxprofit {			maxprofit = p - minprice		}	}	return maxprofit}复制代码

tags: 民间算法 数组 遍历