网站开发面板,常州网站建设推广,高古楼网站找活做,百度免费推广怎么做描述 分析
使用动态规划。dp[i][0] 代表 第i天没有股票的最大利润dp[i][1] 代表 第i天持有股票的最大利润
状态转移方程为#xff1a;dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]); // 前一天没有股票#xff0c;和前一天有股票今天卖掉的最大值dp[i][1] max(dp[i-1…
描述 分析
使用动态规划。dp[i][0] 代表 第i天没有股票的最大利润dp[i][1] 代表 第i天持有股票的最大利润
状态转移方程为dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]); // 前一天没有股票和前一天有股票今天卖掉的最大值dp[i][1] max(dp[i-1][0] - prices[i], dp[i-1][1]); // 前一天没有股票今天买和前一天也有股票的最大值
初始状态dp[0][0] 0; // 第一天不持有股票dp[0][1] prices[0]; // 第一天持有股票需要减去第一天的股票价格
返回值dp[n - 1][0];// 最后一天必须卖掉股票
代码
根据初始状态和状态转移方程写出代码
class Solution {public int maxProfit(int[] prices) {int n prices.length;int[][] dp new int[n][2];dp[0][0] 0;dp[0][1] -prices[0];for (int i 1; i n; i) {dp[i][0] Math.max(dp[i - 1][0], dp[i - 1][1] prices[i]); // 前一天没有股票和前一天有股票今天卖掉的最大值dp[i][1] Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]); // 前一天没有股票今天买和前一天也有股票的最大值}return dp[n - 1][0];// 最后一天必须卖掉股票}
}面试公司
