149.Best Time to Buy and Sell Stock-买卖股票的最佳时机（中等题）

买卖股票的最佳时机

题目

假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。

样例

给出一个数组样例 [3,2,3,1,2], 返回 1

题解

题目意思就是找到一对i,j(i<j)，使得prices[j]-prices[i]最大。 同时迭代记录一个最低价prices[i]和当前的最大利润max，max为下一天的价格减去目前的最低价prices[i]。

public class Solution { /** * @param prices: Given an integer array * @return: Maximum profit */ public int maxProfit(int[] prices) { int max = 0; if (prices.length > 0) { for (int i=0,minPrices = prices[0];i<prices.length-1;i++) { minPrices = Math.min(prices[i],minPrices); max = Math.max(max,prices[i+1]-minPrices); } } return max; } }

Last Update 2016.10.17