四刷 07/2022
Version #2 Constant space DP
重点就是要弄清题意是同一天可以既卖出又买入，而且问的是最多2transactions的profit，一个transaction也是可以的
Time O(N)
Space O(1)
Runtime: 6 ms, faster than 72.73% of Java online submissions for Best Time to Buy and Sell Stock III.
Memory Usage: 77.8 MB, less than 73.50% of Java online submissions for Best Time to Buy and Sell Stock III.
class Solution {
public int maxProfit(int[] prices) {
// max profit that we can get with one transaction on day i
if (prices.length < 2) {
return 0;
}
int minPrice = prices[0];
int maxOneTransac = 0;
int maxDiff = -prices[0];
int max = 0;
// minPrice maxOneTransac maxDiff curr
// 0 1 2 3
for (int i = 1; i < prices.length; i++) {
max = Math.max(max, prices[i] + maxDiff);
minPrice = Math.min(minPrice, prices[i]);
maxOneTransac = Math.max(maxOneTransac, prices[i] - minPrice);
maxDiff = Math.max(maxDiff, maxOneTransac - prices[i]);
}
return max;
}
}
Version #1 Native DP
dp[i - 1][k] -> don't do anything on current day
dp[j][k - 1] + prices[i] - prices[j] -> buy from day j and sell it now
dp[i][k] = Math.max(dp[i - 1][k], dp[j][k - 1] + prices[i] - prices[j])
4.23 %
class Solution {
public int maxProfit(int[] prices) {
// dp[i][k] -> maxProfit we got until day i by using k transactions
// dp[i][k] = Math.max(dp[i - 1][k], dp[j][k - 1] + prices[i] - prices[j])
// dp[0][k] = 0;
// dp[i][0] = 0
if (prices == null || prices.length < 2) {
return 0;
}
int[][] dp = new int[prices.length][3];
for (int k = 1; k <= 2; k++) {
for (int i = 1; i < prices.length; i++) {
int minCost = prices[0];
for (int j = 1; j < i; j++) {
minCost = Math.min(minCost, prices[j] - dp[j][k - 1]);
}
dp[i][k] = Math.max(dp[i - 1][k], prices[i] - minCost);
}
}
return dp[prices.length - 1][2];
}
}
Version #2
Time O(n) Space O(1)
Since we only have 2 transactions, we can use 4 variable to keep track of:
1.The min price we see so far -> for buy in for the 1st transaction
2. The max profit we can get for 1st transaction
3. The min cost we need to pay if we finish the 1st transaction and buy in the 2nd transaction
4. The global max profit we can get from the 2nd transaction
Initial values are:
1.leftMin -> buy at 1st day
2.preMax -> max profit start at 1st day -> buy at 1st day and sell at the same time
3.minCost -> buy at 1st day and sell and then buy in -> what cost us is price[0]
4. max -> buy twice and sell twice at the first day
95.69 %
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int max = 0;
int prevMax = 0;
int minCost = prices[0];
int leftMin = prices[0];
for (int price : prices) {
// What is the min price on the left so far
leftMin = Math.min(price, leftMin);
// What is the max we can get for 1 transaction
prevMax = Math.max(prevMax, price - leftMin);
// What is the min Cost for 1 transaction + 1 buy in
minCost = Math.min(minCost, price - prevMax);
max = Math.max(max, price - minCost);
}
return max;
}
}
二刷
DP
Before Optimize:
Kadane's Algorithm, 求 maximum subarray of diff
Walk from left to right to get maximum subarray ends with index i
Walk from right to left to get maximum subarray starts with index i
-> Walk from left to right
-> 用一个max记录max of maximum subarray ends with index i
-> 这个max与maximum subarray starts with index i的和就是当前可以的到的最大profit
Time O(3n)
Space O(2n)
后来发现可以优化，只需要扫两遍
93.13 %
class Solution {
public int maxProfit(int[] prices) {
// Split from the middle
// maxProfit end at current index and maxProfit start at current index + 1
if (prices == null || prices.length < 2) {
return 0;
}
int[] endWithIndex = new int[prices.length];
int[] startWithIndex = new int[prices.length];
for (int i = 1; i < prices.length; i++) {
endWithIndex[i] = prices[i] - prices[i - 1] + (endWithIndex[i - 1] > 0 ? endWithIndex[i - 1] : 0);
}
for (int j = prices.length - 2; j >= 0; j--) {
startWithIndex[j] = prices[j + 1] - prices[j] + (startWithIndex[j + 1] > 0 ? startWithIndex[j + 1] : 0);
}
int leftMax = 0;
int max = 0;
for (int split = 0; split < prices.length ; split++) {
leftMax = Math.max(leftMax, endWithIndex[split]);
max = Math.max(max, leftMax + startWithIndex[split]);
}
return max;
}
}
After optimized:
发现这个方法和一刷的基本一样的
果然是无招胜有招 啊
55.99 %
Time O(2n)
Space O(n)
class Solution {
public int maxProfit(int[] prices) {
// Split from the middle
// maxProfit end at current index and maxProfit start at current index + 1
if (prices == null || prices.length < 2) {
return 0;
}
int[] startWithIndex = new int[prices.length];
for (int j = prices.length - 2; j >= 0; j--) {
startWithIndex[j] = prices[j + 1] - prices[j] + (startWithIndex[j + 1] > 0 ? startWithIndex[j + 1] : 0);
}
int leftMax = 0;
int max = 0;
int dp = 0;
for (int split = 0; split < prices.length ; split++) {
if (split != 0) {
int currDP = prices[split] - prices[split - 1] + (dp > 0 ? dp : 0);
dp = currDP;
}
leftMax = Math.max(leftMax, dp);
max = Math.max(max, leftMax + startWithIndex[split]);
}
return max;
}
}
一刷
You may complete at most two transactions.
是一个比较常规的思路，因为要做两个transactions所以应该是以某一个index作为分割点，左边的maxProfit与右边的maxProfit相加
很容易想到的是那个左扫一遍记录一个array然后右扫一遍的同时比较出max的思路
好像是蓄水那道题吧
感觉这个不是dp的方法，不知道dp怎么做
哦！如果是半个dp的话就是左扫一遍的时候做dp，但是完全dp的方法还是不知道
77.56 %
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) return 0;
//leftMaxProfit[i] maxprofit in day[0, i]
//rightMaxProfit[i] maxprofit in day[i, 0]
int length = prices.length;
int[] leftMaxProfit = new int[length];
int leftMinPrice = prices[0];
/*2 1 3 4 5 4 2 8 7
leftMinPrice 2 2 1 1 1 1 1 1 1
leftMaxProfit 0 0 2 3 4 3 1 7 6
max 7 0
rightMaxPrice 8 8 7
rightMaxProfit 6 0 0
*/
for (int i = 1; i < length; i++) {
if (prices[i] > leftMinPrice) {
leftMaxProfit[i] = Math.max(leftMaxProfit[i - 1], prices[i] - leftMinPrice);
} else {
leftMinPrice = prices[i];
leftMaxProfit[i] = leftMaxProfit[i - 1];
}
}
int max = 0;
int rightMaxPrice = prices[length - 1];
int rightMaxProfit = 0;
for (int i = length - 2; i >= 0; i--) {
if (prices[i] < rightMaxPrice) {
rightMaxProfit = Math.max(rightMaxProfit, rightMaxPrice - prices[i]);
} else {
rightMaxPrice = prices[i];
}
max = Math.max(max, rightMaxProfit + leftMaxProfit[i]);
}
return max;
}
}
No comments:
Post a Comment