网站源码下载插件,普陀企业网站建设,郑州锐途网站建设,手机电商平台怎么做的题意理解#xff1a; 已知#xff1a;一个整数数组 prices #xff0c;其中 prices[i] 表示某支股票第 i 天的价格 如何哪个时间点买入#xff0c;哪个时间点卖出#xff0c;多次交易#xff0c;能够收益最大化 目的#xff1a;收益最大化 解题思路#xff1a; 使用贪心… 题意理解 已知一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格 如何哪个时间点买入哪个时间点卖出多次交易能够收益最大化 目的收益最大化 解题思路 使用贪心思路来解题需要明确什么时局部最优解如何由局部最优解推导全局最优解。 首先我们要尽可能的利益最大化就要尽可能的保证利益为正。 这里引入利益区间的概念及[买入卖出] 利益卖出-买入 例如 [7,1,5,3,6,4] eg:利益区间[0,3] 利益p[3]-p[0] p[3]-p[2]p[2]-p[1]p[1]-p[0] 实际是每天利益的和由此可知我们要保证利益尽可能的大 即收集所有正的天利益即可得到这个规定时间内的最大获益。 1.贪心解题 我们使用result来记录最大利益同时我们需要两个指针一个指向买入天一个指向卖出天来计算当前交易利益 注意若交易会损失钱则可选择不交易所以result的初始化为0。
public int maxProfit(int[] prices) {int result0;//第一天不卖出最后一天不买入for(int i1;iprices.length;i){resultMath.max(prices[i]-prices[i-1],0);//总是叠加正的利益}return result;}
2.分析 时间复杂度O(n) 空间复杂度O(n) n是prices数组的长度。
