Home >Java >javaTutorial >LeetCode Day Dynamic Programming Part 9
You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.
Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:
Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Constraints:
1 <= k <= 100
1 <= prices.length <= 1000
0 <= prices[i] <= 1000
Original Page
public int maxProfit(int k, int[] prices) { /**[0][0] do nothing in day 0 [0][1] own the stock for 1st time in day 0 [0][2] not own the stock for 1st time in day 0 [0][3] own the stock for 2nd time in day 0 [0][4] not own the stock for 2nd time in day 0 .... [0][k*2-1] own the stock for kth time in day 0 [0][k*2] not own the stock for kth time in day 0 [1][1] = max([0][1],[0][0]-prices[1]) [1][2] = max([0][2],[0][1]+prices[1]) [1][3] = max([0][3],[0][2]-prices[1]) [i][j] if j is odd means we need to pay for the stock or keep the own status if j is even means we can sell the stock or keep the non-stock status */ int[][] dp = new int[prices.length+1][k*2+1]; for(int i=1; i<=k*2; i+=2){ dp[0][i] = -prices[0]; } for(int i=1; i<prices.length; i++){ for(int j=1; j<=k*2; j++){ dp[i][j] = Math.max( dp[i-1][j], dp[i-1][j-1] + ((j % 2 == 0) ? 1 : -1) * prices[i] ); } } return dp[prices.length-1][k*2]; }
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:
After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
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,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]
Example 2:
Input: prices = [1]
Output: 0
Constraints:
1 <= prices.length <= 5000
0 <= prices[i] <= 1000
public int maxProfit(int[] prices) { /** [0] own the stock [1] colldown [2] not own the stock */ int[][] dp = new int[prices.length][3]; dp[0][0] = -prices[0]; for(int i=1; i<prices.length; i++){ dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2]-prices[i]); dp[i][1] = dp[i-1][0] + prices[i]; dp[i][2] = Math.max(dp[i-1][1], dp[i-1][2]); } // Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println); return Math.max(dp[prices.length-1][2],dp[prices.length-1][1]); }
Be careful, that when it is cooldown, we cannot buy a new stock.
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).
The transaction fee is only charged once for each stock purchase and sale.
Example 1:
Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6
Constraints:
1 <= prices.length <= 5 * 10^4
1 <= prices[i] < 5 * 10^4
0 <= fee < 5 * 10^4
Original Page
the only thing we should consider is to add the transaction fee, but the fee will not change our previous logic
public int maxProfit(int[] prices, int fee) { int[] dp = new int[2]; int temp = 0; dp[0] = -prices[0]; for(int i=1; i<prices.length; i++){ temp = dp[1]; dp[1] = Math.max(dp[1], dp[0] + prices[i] -fee); dp[0] = Math.max(dp[0], temp-prices[i]); } return dp[1]; }
The above is the detailed content of LeetCode Day Dynamic Programming Part 9. For more information, please follow other related articles on the PHP Chinese website!