[LeetCode]Best Time to Buy and Sell Stock做题笔记

发布于:2021-11-29 21:42:21

1、Best Time to Buy and Sell Stock

题意:给定一个数组,该数组为每天股票的价格,求解出你最大的收益是多少(哪一天买,哪一天卖可以获得最多的盈利),最多只能持有一笔交易。


分析:该题目可以转化为求最大和的类型,后面一天减去前面一天的股价,即可得到两天之间的收益,求出该收益序列的连续子序列最大和即可。


临界条件:如果数组只有一个元素,表示收益为0;如果计算出的收益为负数,依然返回0.


代码:




int maxProfit(vector &prices) {
if(prices.size() < 1)
{
return 0;
}
int last = 0;
int max = 0;
for(int i = 0; i < prices.size()-1; ++i)
{
int prof = prices[i+1]-prices[i];
last = prof > last + prof ? prof : last + prof;
max = max > last ? max : last;
}

return max > 0 ? max : 0;
}



还有另外一种思路,要求最大的收益,自然是用最高的股票价格减去最低的价格即可,考虑到时间的因素,当前的收益一定是当天价格减去前面几天里的最低价格即可。


所以产生了如下代码:



int maxProfit(vector &prices) {

if(prices.size() < 1)
{
return 0;
}
int minVal = prices[0];
int max = 0;
for(int i = 1; i < prices.size(); ++i)
{
max = max > prices[i] - minVal ? max : prices[i]-minVal;
minVal = minVal < prices[i] ? minVal : prices[i];
}

return max > 0 ? max : 0;
}


2、Best Time to Buy and Sell Stock I

题意:给定条件同1,只是可以进行任意多的交易,不限交易次数,但是同时进行的交易只能有一个


分析:该题目只要理解了题意,就很简单,可以进行任意笔的交易,则就是把相邻两天收益为正数的累加即可。


边界条件:同1


代码:


int maxProfit(vector &prices) {
if(prices.size() <= 1)
{
return 0;
}
int max = 0;
for(int i = 0; i < prices.size()-1; ++i)
{
int element = prices[i+1]-prices[i];
if(element > 0)
{
max += element;
}
}
return max > 0 ? max : 0;
}



3、Best Time to Buy and Sell Stock II

题意:本题目的限制条件修改为最多只能进行两次交易,两次交易时间不能有重叠


分析:这一题的难度提升,此问题可以分解为两个子问题:假设要计算第5天的收益,则可以分解为第5天之前的最大收益与第5天之后的最大收益,两者相加,则为以第5天作为第一次交易与第二次交易的临界,所得的最大收益,如果知道给定数组里每一天的最大收益,其中最大的那个即为数组内所有天数里的收益最大值。


起初,借鉴编程之美中,求子序列最大和的思想,写出了如下代码:


?


class Solution {
public:
int maxProfit(vector &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(prices.size() < 2)
{
return 0;
}
if(prices.size() == 2)
{
return prices[1]-prices[0] > 0 ? prices[1]-prices[0] : 0;
}

vector sub_pris = vector();

for (int i = 0; i < prices.size()-1; ++i)
{
sub_pris.push_back(prices[i+1]-prices[i]);
}
int num = sub_pris.size();
vector all;
all.resize(num);

all[0] = sub_pris[0];
int last = sub_pris[0];
for(int i = 1; i < sub_pris.size(); ++i)
{
last = max(sub_pris[i], last+sub_pris[i]);
all[i] = max(all[i-1], last);
}

int ret_max = 0;
int before = sub_pris[num-1];
int start = sub_pris[num-1];
for(int i = num - 2; i >= 0; --i)
{
start = max(sub_pris[i], start+sub_pris[i]);
before = max(start, before);
int curall = i >= 1?all[i-1]:0;
if(before + curall > ret_max)
ret_max = before + curall;
}
return ret_max>0?ret_max:0;

}

int max(int a, int b)
{
return a > b ? a : b;
}
};



上面代码中,先求出相邻天的收益数组,然后分别从左向右、从右向左求出子序列最大和,逻辑清晰,但是实现稍微复杂一些。


借鉴第一小节的方法,写出了代码2,相对与上面的代码,逻辑比较清晰一些。



int maxProfit(vector &prices) {
if(prices.size() < 2)
{
return 0;
}
if(prices.size() == 2)
{
return prices[1]-prices[0] > 0 ? prices[1]-prices[0] : 0;
}

vector all;
all.resize(prices.size()-1);
int minVal = prices[0];
for(int i = 1; i < prices.size(); ++i)
{
int tmpmax = i>=2?all[i-2]:0;
if(prices[i] - minVal > tmpmax)
all[i-1] = prices[i]-minVal;
else
all[i-1] = tmpmax;

if(minVal > prices[i])
minVal = prices[i];
}

int maxVal = prices[prices.size()-1];
int max = 0;
int ret_max = 0;
for(int i = prices.size()-2; i >= 0; --i)
{
max = maxVal - prices[i] > max ? maxVal - prices[i] : max;
int cmp = max;
if(i >= 1)
{
cmp += all[i-1];
}
if(ret_max < cmp)
ret_max = cmp;

if(prices[i] > maxVal)
maxVal = prices[i];
}
return ret_max>0?ret_max:0;
}


以上代码在LeetCode中可通过所有的test case,发出来供大家参考。


相关推荐

最新更新

猜你喜欢