亿通网站建设,怎样把自己做的网站上传到网上,wordpress制作左侧边栏,湖北荆门建设银行网站一、题目分析 给定一个整数数组prices#xff0c;其中第 prices[i] 表示第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下#xff0c;你可以尽可能地完成更多的交易#xff08;多次买卖一支股票#xff09;: 卖出股票后#xff0c;你无法在第二…一、题目分析 给定一个整数数组prices其中第 prices[i] 表示第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下你可以尽可能地完成更多的交易多次买卖一支股票: 卖出股票后你无法在第二天买入股票 (即冷冻期为 1 天)。 注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 从题目中可以知道一个状态基 示例分析 输入: prices [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] 二、算法分析
1.状态表示题目要求经验 2.根据状态基图填写状态转移方程 3.初始化 1.当在第0天的时候买入dp[0][0]-p[0]; 2.当在第0天的时候可交易dp[0][0]0;//啥也不干 3.当在第0天的时候冷冻期dp[0][0]0;//买了又卖 4.返回值
返回三种状态下的最大值也可只返回最后两个
三、代码实现
public int maxProfit(int[] prices) {int lenprices.length;//创建dp表,三行0-》买入状态下的最大值1-》可交易状态下的最大值 2-》处于冷冻期的最大利润int[][] dpnew int[len1][3];//初始化,当在第0天的状态下买入为-p【0】可交易啥也不干出入卖出买了又卖0dp[0][0]-prices[0];//填表for(int i1;ilen1;i){dp[i][0]Math.max(dp[i-1][0],dp[i-1][1]-prices[i-1]);dp[i][1]Math.max(dp[i-1][1],dp[i-1][2]);dp[i][2]dp[i-1][0]prices[i-1];}//返回值return Math.max(dp[len][1],dp[len][2]);}
