05 August 2008
Say you have an array for which the i_th 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:
1
2
3
4
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:
1
2
3
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
卖需要在买之后，一遍循环过去后先对比之前的buy的最小值和当前值得到当前最小buy，然后当前的price减去当前最小的buy得到利润，保留最大的利润值。这大概是最简单的动态规划的思想了。
DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
// dp[i][j][k]: i - day, j - tranaction times, k - whether have stocks on hand
public int maxProfit(int[] prices) {
int maxProfix = 0;
if (prices == null || prices.length == 0) {
return maxProfix;
}
int len = prices.length;
//ith day，没有价格无法计算属于上面corner cases，这里不用len + 1
int[] dp = new int[len];
dp[0] = 0; // profit为0，尚未开始买卖
int minPrice = prices[0];
for (int i = 1; i < len; i++) {
dp[i] = Math.max(dp[i - 1], prices[i] - minPrice);
minPrice = Math.min(minPrice, prices[i]);
}
return dp[len - 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 == null || prices.length == 0) {
return 0;
}
int minPrice = prices[0];
int maxP = Integer.MIN_VALUE;
// 跟上面不同，这里第ith day还没有值，从第0个开始
for (int i = 0; i < prices.length; i++) {
maxP = Math.max(maxP, prices[i] - minPrice);
minPrice = Math.min(minPrice, prices[i]);
}
return maxP;
}
}