https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2)
return 0;
int max = 0;
int low = prices[0];
for (int day = 1; day < prices.length; day++) {
max = Math.max(max, prices[day] - low);
low = Math.min(low, prices[day]);
}
return max;
}
}https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2)
return 0;
int max = 0;
for (int day = 1; day < prices.length; day++) {
max += Math.max(prices[day] - prices[day-1], 0);
}
return max;
}
}https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
class Solution(object):
def maxProfit(self, prices):
if not prices or len(prices) < 2:
return 0
n = len(prices)
p1, p2 = [0] * n, [0] * n
lowest = prices[0]
for i in range(1, n):
p1[i] = max(p1[i], prices[i] - lowest)
lowest = min(lowest, prices[i])
highest = prices[n - 1]
for j in range(n-2, -1, -1):
p2[j] = max(p2[j + 1], highest - prices[j])
highest = max(highest, prices[j])
maxProfit = 0
for i in range(n):
maxProfit = max(maxProfit, p1[i] + p2[i])
return maxProfithttps://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
-
动态规划，
max[K][day]表示截止到第 day 天一共交易 K 次的最大利润 -
进一步优化（降维）：因为第 K 次交易只与 K-1 次有关，所以只需要两个滚动数组记录 max[day] 即可。这里把上一步中的二维的DP降维成两个一维数组。
lastTransMax[day]：前一次交易第 day 天的最大利润currTransMax[day]：当前交易到第 day 天的最大利润
-
DP方程：我们选择在第 day 天交易（即卖出，因为买进可看作是亏钱）或者不交易，即:
currTransMax[day] = Math.max(maxRemaining + prices[day], currTransMax[day-1])
- 如果我们发现 K 过大，即 K 大于交易天数的一半，则可看成是无限次交易，因为一次完整的交易最少也需要2天，一买一卖，那么 N 天最多也只能进行 N/2 次交易，所以K > N/2 的这种情况可以当成无限次交易来完成。参考 122. Best Time to Buy and Sell Stock II
class Solution {
public int maxProfit(int k, int[] prices) {
// corner case
if (k == 0 || prices == null || prices.length < 2)
return 0;
// check k if too large
if (k > prices.length / 2) {
int max = 0;
for (int i = 1; i < prices.length; i++) {
max += Math.max(prices[i]-prices[i-1], 0);
}
return max;
}
int days = prices.length;
// 滚动数组
int[] lastTransMax = new int[days];
int[] currTransMax = new int[days];
for (int trans = 1; trans <= k; trans++) {
int maxRemaining = -prices[0];
for (int day = 1; day < days; day++) {
currTransMax[day] = Math.max(maxRemaining + prices[day], currTransMax[day-1]);
maxRemaining = Math.max(maxRemaining, lastTransMax[day] - prices[day]);
}
lastTransMax = currTransMax;
currTransMax = new int[days];
}
return lastTransMax[days-1];
}
}https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.
Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
Example 2:
Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6
Constraints:
1 < prices.length <= 5 * 1040 < prices[i], fee < 5 * 104
class Solution {
public int maxProfit(int[] prices, int fee) {
int n = prices.length;
int[][] f = new int[n + 1][2];
int INT_MIN = Integer.MIN_VALUE;
for (int i = 0; i < f.length; i++)
Arrays.fill(f[i], INT_MIN);
f[0][0] = 0;
int ans = 0;
for (int i = 1; i <= n; i++) {
f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] + prices[i - 1]);
f[i][1] = Math.max(f[i - 1][1], f[i - 1][0] - prices[i - 1] - fee);
ans = Math.max(ans, f[i][0]);
}
return ans;
}
}