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; }}新闻热点
疑难解答
