Say you have an array for which the ith element is the PRice of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most k transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
一刷沒ac 解題思路：dp[i][j]代表前j(索引為j)天進行i次交易的最大利潤。假設在 j 天賣出，最大利潤dp[i][j] = Math.max(dp[i][j-1], prices[j] + tmp); tmp是上次交易(買入)剩下的利潤，tmp = Math.max(tmp, dp[i-1][j-1] - prices[j]);
public class Solution { public int maxProfit(int k, int[] prices) { //if(k < 0 || prices == null || prices.length == 0) return 0; int len = prices.length; if(k >= len/2) return uniquesolve(prices); int[][] dp = new int[k+1][len]; for(int i = 1; i <= k; i++){ int tmp = -prices[0]; for(int j = 1; j < len; j++){ dp[i][j] = Math.max(dp[i][j-1], prices[j] + tmp); tmp = Math.max(tmp, dp[i-1][j-1] - prices[j]); } } return dp[k][len-1]; } public int uniquesolve(int[] prices){ int res = 0; for(int i = 1; i < prices.length; i++){ if(prices[i] > prices[i-1]) res += prices[i] - prices[i-1]; } return res; }}新聞熱點
疑難解答
