php-leetcode题解之买卖股票的最佳时机.zip

<?php /* * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。 注意你不能在买入股票前卖出股票。 示例 1: 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 示例 2: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。 */ class Solution { /** * @param Integer[] $prices * @return Integer */ function maxProfit($prices) { $maxPrice = 0; $min = $prices[0]; for ($i = 0; $i < count($prices); $i++) { if ($prices[$i] < $min) { $min = $prices[$i]; } else { $tempPrice = $prices[$i] - $min; if ($tempPrice > $maxPrice) { $maxPrice = $tempPrice; } } } return $maxPrice; } /** * dp 动态规划的写法 * @param $prices * @return int|mixed */ function maxProfit1($prices) { if (empty($prices)) return 0; // 0，没买，1 买入一股没卖，2。之前买了现在卖了。 $profit[0][0] = 0; // 没买没卖之前 $profit[0][1] = -$prices[0]; // 买入一股没卖 $profit[0][2] = 0; //之前买了现在卖了。 $maxPrice = 0; // 最大金额 for ($i = 1; $i < count($prices); $i++) { // 没买股票 前一天 $profit[$i][0] = $profit[$i - 1][0]; // 买入股票，可以不动（之前已经买过了股票）或者是 前一天没买股票，这一天要买股票，所以要减去购买的金额 $profit[$i][1] = max($profit[$i - 1][1], $profit[$i - 1][0] - $prices[$i]); // 卖了股票，前一天（已经买入的时候的）加上套现的金额 $profit[$i][2] = $profit[$i - 1][1] + $prices[$i]; // 每一步，拿出来最大金额 $maxPrice = max($maxPrice, $profit[$i][0], $profit[$i][1], $profit[$i][2]); } return $maxPrice; } } $Solution = new Solution(); $prices = [7, 1, 5, 3, 6, 4]; echo $Solution->maxProfit($prices); echo $Solution->maxProfit1($prices);