广州地区做网站的,深圳外贸推广公司,学习通网页版,公司网站管理属于什么职位题意理解#xff1a; 给定一个数组 prices #xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交… 题意理解 给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。 注意这里只有一只股票只进行一次买卖求最大利益。 所以对于每一天都有两个状态持有股票、不持有股票 这里定义一个二维dp数组dp[0]表示持有股票能获得的最大收益dp[0]表示不持有股票能获得最大大受益。 对于不持有股票的状态包含当天卖出 持有股票状态包含当前买入 解题思路 定义二维dp[]数组 dp[i][0]:表示持有股票能获得的最大收益 dp[i][1]:表示不持有股票能获得最大大受益 1.初始化 dp[0][0]-price[0];//买入所以当前收益为负 dp[0][1]0;//无交易无收益 2.递推公式 dp[i][0]max(之前买入当前买入)max(dp[i-1][0],-prices[i]) dp[i][1]max(之前卖出今天卖出)max(dp[i-1][1],dp[i-1][0]prices[i]) 1.解题
public int maxProfit(int[] prices) {int[][] dpnew int[prices.length][2];dp[0][0]-prices[0];dp[0][1]0;for(int i1;iprices.length;i){dp[i][0]Math.max(dp[i-1][0],-1*prices[i]);dp[i][1]Math.max(dp[i-1][1],dp[i-1][0]prices[i]);}return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]);}
2.分析 时间复杂度O(n) 空间复杂度O(2n)
