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.
买卖股票。题意是给一个数组，它的第i个元素是这只股票第i天的价格。你最多允许完成一次交易（一买一卖），求问你所能获取的最大利润是多少。注意只能先买后卖。这个题有两种做法，一个只是单纯扫描一遍数组来扫描，找到最大的差值；另一个是动态规划。
扫描法是设第一个元素是最低价，然后往后扫描。扫描的时候记住利润profit = 当前价格 - 最低价。
时间O(n)
空间O(1)
JavaScript实现
1 /** 2 * @param {number[]} prices 3 * @return {number} 4 */ 5 var maxProfit = function (prices) { 6 // corner case 7 if (prices === null || prices.length < 2) return 0; 8 9 // normal case 10 let min = prices[0]; 11 let profit = 0; 12 for (let price of prices) { 13 min = Math.min(min, price); 14 profit = Math.max(profit, price - min); 15 } 16 return profit; 17 };
Java实现
1 class Solution { 2 public int maxProfit(int[] prices) { 3 // corner case 4 if (prices == null || prices.length < 2) { 5 return 0; 6 } 7 8 // normal case 9 int min = prices[0]; 10 int profit = 0; 11 for (int price : prices) { 12 min = Math.min(min, price); 13 profit = Math.max(profit, price - min); 14 } 15 return profit; 16 } 17 }
动态规划的做法如下。设一个二维数组dp[][]其中第一维的长度是数组的长度len，第二维的长度是2，只有可能是0或1。这里第一维代表的就是遍历到某个位置的DP值，第二维表示的是在当前位置是否持有股票。持有记为1，不持有记为0。注意这里的不持有不是一直不买，而是卖出之后的不持有。我参考了这个更详细的解释，写的非常好。
这里DP值的更新细节如下
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
这一行的意思是在某一个位置如果不持有股票，那么他的DP值有可能是因为上一个位置也是不持有股票，或者是当前位置卖了股票而得到的
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
这一行的意思是在某一个位置如果持有股票，那么他的DP值有可能是因为上一个位置也持有股票，或者是当前位置买了股票导致的。这里为什么买了股票却减prices[i]，你可以把这里的负号理解为用户的成本，买了股票自然成本为负了。
时间O(n)
空间O(n)
Java实现
1 class Solution { 2 public int maxProfit(int[] prices) { 3 int len = prices.length; 4 if (len < 2) { 5 return 0; 6 } 7 // 0：用户手上不持股所能获得的最大利润，特指卖出股票以后的不持股，非指没有进行过任何交易的不持股 8 // 1：用户手上持股所能获得的最大利润 9 // 注意：因为题目限制只能交易一次，因此状态只可能从 1 到 0，不可能从 0 到 1 10 int[][] dp = new int[len][2]; 11 dp[0][0] = 0; 12 dp[0][1] = -prices[0]; 13 for (int i = 1; i < len; i++) { 14 dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); 15 dp[i][1] = Math.max(dp[i - 1][1], -prices[i]); 16 } 17 return dp[len - 1][0]; 18 } 19 }