首页 > 代码库 > [leetcode]_Best Time to Buy and Sell Stock I && II
[leetcode]_Best Time to Buy and Sell Stock I && II
一个系列三道题,我都不会做,google之答案。过了两道,第三道看不懂,放置,稍后继续。
一、Best Time to Buy and Sell Stock I
题目:一个数组表示一支股票的价格变换。要求只买卖一次,获得最大收益。
思路:一开始我认为是寻找最大、最小值,但由于最大值不一定总是出现在最小值的后面,因此WA。
参考思路:DP。对第i个价格,减去前i-1个价格中的最小值(保证该收益是在第i个价格卖出的最大收益),其收益与之前获得的最大收益相比。
代码:
1 public int maxProfit(int[] prices) { 2 int len = prices.length ; 3 if(len < 2) return 0; 4 5 int min = prices[0] ; 6 int maxProfit = 0; 7 8 for(int i = 1 ; i < len ; i++){ 9 int temp = prices[i] - min; //当前值减去前i-1个值的最小值 10 if(maxProfit < temp) maxProfit = temp; //更新最大收益 11 if(prices[i] < min) min = prices[i]; //看是否需要更新前i个值的min值,用于下次循环 12 } 13 14 return maxProfit; 15 }
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
二、Best Time to Buy and Sell Stock II
题目:在上一题的基础上,允许对一支股票任意次买卖,(同一时间可先卖出再马上买入),同样求最大收益。
思路:如果第i个价格大于第i-1个价格,则将此部分收益加入到最大收益中,因为可以在第i个价格处马上卖出再马上买入。
代码:
1 public int maxProfit(int[] prices) { 2 int profit = 0; 3 for(int i = 1 ; i < prices.length ; i++){ 4 if(prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1]; 5 } 6 return profit; 7 }
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
三、待续
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。