首页 > 代码库 > [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 }

 

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

三、待续