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)。
