给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 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
| 输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
|
来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：
本题思想其实很简单，就是低买高卖。具体来说，我们只需要在股票价格最低时买入，在高价时卖出，但是这里需要注意一点就是，低价购入的时机必须出现在高价卖出之前，不然没有意义。基于以上的思路，我们很容易就能写出代码。
具体代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0;
int minProfit = Integer.MAX_VALUE;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minProfit) {
minProfit = prices[i];
}
if (prices[i] - minProfit > maxProfit) {
maxProfit = prices[i] - minProfit;
}
}
return maxProfit;
}
}
|
记录一下动态规划的解法，每天(除了第一天之外)只有三种状态，即买入、休息、卖出，那么限制只能持有一只股票，那么每天的状态就分为两种，
所以此时的最大利润就是前一天持有股票时的最大利润和当前买入一支股票后获得的最大利润中的较大值。状态转移方程为：
- 第二种状态是当天没有持有股票获得的最大利润，这种也分为两种：
- 一是今天休息，即前一天也没有持有股票
- 二是今天卖出了一支股票，获取了利润
所以此时的最大利润就是前一天没有持有股票的最大利润和当天卖出一支股票后获得的最大利润中的较大值。状态转移方程为：
那么我们可以用一个二维数组来记录每天是否持有股票时获得的最大利润，这里注意边界条件，即T[0][0]表示第一天没有持有股票能获取的最大利润，此时自然为0，T[0][1]表示第一天就买入了一支股票能获取的最大利润， 此时就是第一天股票的价格的负数，即亏损。
具体代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) return 0;
int[][] T = new int[prices.length][2];
T[0][0] = 0;
T[0][1] = -prices[0];
for (int i = 1; i < prices.length; i++) {
T[i][0] = Math.max(T[i - 1][0], T[i - 1][1] + prices[i]);
T[i][1] = Math.max(T[i - 1][1], - prices[i]);
}
return T[prices.length - 1][0];
}
}
|
由于当天状态之和前一天状态有关，那么我们可以将空间复杂度降到常量范围，即用两个整型变量保存是否持有股票的两种收益。
具体代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) return 0;
int notHave = 0;
int have = -prices[0];
for (int i = 1; i < prices.length; i++) {
notHave = Math.max(notHave, have + prices[i]);
have = Math.max(have, -prices[i]);
}
return notHave;
}
}
|
