1. question: 买卖股票的最佳时机(简单)
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock
示例 1:
1 2 3 4
| 输入:[7,1,5,3,6,4] 输出:5 解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
|
示例 2:
1 2 3
| 输入:prices = [7,6,4,3,1] 输出:0 解释:在这种情况下, 没有交易完成, 所以最大利润为 0。
|
提示:
1 2
| 1 <= prices.length <= 105 0 <= prices[i] <= 104
|
2. answers
这道题和以前的做的买卖股票II类似。只不过本题要求只能买卖一次,但是思路,以贪心的方式来做的话,还是一样的。
注意,单天买入卖出相当于连续多天持有。因此,计算单天的收益,累加收益,每次取最大值。
如果收益结果为负数,说明累加到现在,收益为负数了,显然应该重新计算收益,即清零。再次累加,取最大值。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| public class Solution_0132 {
public int maxProfit(int[] prices) {
if(prices.length <= 1) return 0;
int sums = 0; int maxValue = 0;
int[] diff = new int[prices.length - 1]; for (int i = 1; i < prices.length; i++) { diff[i-1] = prices[i] - prices[i-1]; }
for (int value : diff) {
sums += value; if (sums >= 0) maxValue = Math.max(maxValue, sums); else sums = 0; }
return maxValue; }
public static void main(String[] args) { System.out.println();
int[] prices = {7, 6, 4, 3, 1};
Solution_0132 s = new Solution_0132();
System.out.println(s.maxProfit(prices)); } }
|
参考题解,其实贪心还有另一种方式。既然收益最大,显然买入的时候是左侧最小的,卖出的时候是右侧最大的即可。
因此,可遍历数组,每次取最小值,并计算收益(取最大值)。【因为后面的可能比当前的大,所以此时最小值就不变】,计算收益,显然是当前值卖出,【即现在卖出,时刻取收益最大值】。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| public class Solution_0132_03 {
public int maxProfit(int[] prices) {
int maxValue = 0; int low = Integer.MAX_VALUE;
for (int i = 0; i < prices.length; i++) {
low = Math.min(low, prices[i]); maxValue = Math.max(maxValue, prices[i] - low); }
return maxValue; }
public static void main(String[] args) {
System.out.println();
Solution_0132_03 s = new Solution_0132_03();
int[] prices = {7, 1, 5, 3, 6, 4};
System.out.println(s.maxProfit(prices)); } }
|
那么动态规划该怎么做呢?
1 2 3 4 5
| * 参考题解,动态规划:前i天的最大收益 = max{前i-1天的最大收益,第i天的价格-前i-1天中的最小价格} * 其实本题是找最大值。那么既然遍历到了当天,那么就需要计算当天卖出的收益【怎么知道当天的最大收益呢?只需要找到前面的最低价格即可】。 * 既然有前到后遍历到这,所以肯定能找到最小值。即本天卖出的最大收益可计算到。 * * 但是前面卖出也有最大值,因此,需要比较取最大值。其实和02解法是一样的思路。
|
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| public class Solution_0132_04 {
public int maxProfit(int[] prices) {
int min = 0;
int[] dp = new int[prices.length];
dp[0] = Integer.MIN_VALUE;
for (int i = 1; i < prices.length; i++) {
if(prices[i] < prices[min]) min = i;
dp[i] = Math.max(dp[i-1], prices[i] - prices[min]); }
return Math.max(0, dp[prices.length - 1]); }
public static void main(String[] args) { System.out.println();
Solution_0132_04 s = new Solution_0132_04();
int[] prices = {7,6,4,3,1};
System.out.println(s.maxProfit(prices)); } }
|
以二维数组,动态规划做一下。每一天的状态只有两个:持有股票、不持有股票。可定义数组dp[i][0]表示第i天持有股票时的最大利润,dp[i][1]表示第i天不持有股票的最大利润。
- dp[i][0]只能由前一天持有股票;或者今天买入,即
dp[i][0]=max(dp[i-1][0], -prices[i])
。不能由前一天不持有股票,今天买入股票
得到,因为只能交易一次,显然,今天买入,可能会是第二次交易。
- dp[i][1]可由前一天持有股票,今天卖出;或者前一天不持有股票,二者取最大值得到。即
dp[i][1]=max(dp[i-1][1], dp[i-1][0] + prices[i])
初始化,第0天dp[0][0] = -prices[0]; dp[0][1] = 0
,
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| public class Solution_0132_06 {
public int maxProfit(int[] prices) {
int[][] dp = new int[prices.length][2]; dp[0][0] = -prices[0]; dp[0][1] = 0;
for (int i = 1; i < prices.length; i++) {
dp[i][0] = Math.max(dp[i-1][0], -prices[i]);
dp[i][1] = Math.max(dp[i-1][1], dp[i][0] + prices[i]); }
return dp[dp.length - 1][1]; }
public static void main(String[] args) { System.out.println();
int[] prices = {7,1,5,3,6,4};
Solution_0132_06 s = new Solution_0132_06();
System.out.println(s.maxProfit(prices)); } }
|
3. 备注
参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com),代码随想录 (programmercarl.com)。