[Leetcode] Best time to buy and sell stock ii 买卖股票的最佳时机

时间:2022-01-06 08:47:25

Say you have an array for which the i th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

题意:可以做多次交易,但必须是做完一次交易了,再做下一次。

思路:这个要注意和显示生活中区别,这里是每天股票的价格已经知道了,所以,买卖的时候,只要是盈利的都做。大致过程是,对相邻两天的股票价格比较,只要后者大于前者,这次买卖就做。代码如下:

 class Solution {
public:
int maxProfit(vector<int> &prices)
{
int profit=;
int len=prices.size();
for(int i=;i<len-;++i)
{
if(prices[i+]-prices[i]>)
profit+=prices[i+]-prices[i];
}
return profit;
}
};

这里值得注意的是:若代码中第6、7两行写成如下形式,是不能AC的。个人认为是prices.size()的类型为vector<int>::size_type,而减1以后,在prices.size()=0的情况,会负溢出。导致i小于一个正整数,但是数组中没有值,对数组进行访问时,会发生段问题。

(自己的考虑,没有考虑到类型限制,详情见下面)

 for(int i=;i<prices.size()-;++i)
{
......
}

在本地验证的代码:

 #include<iostream>
#include<vector> using namespace std; int main()
{
vector<int> a ;
cout << a.size() - << endl;
return ;
} //输出42949647295

解决的方法:一、之前加if判断,二、使用最上面代码中的那种方式--先求数组大小,然后用这个值去参与for循环。

//更新

这里给出Grandyang的回答:因为prices.size()返回的是size_type型的,这是一种unsigned类型,也就是无符号类型,所以在直接对其做减法是不行的,因为负数对其来说不合法,所以我们可以先强制将其转为整型,再做法,比如:

 for(int i = ; i < (int)prices.size() - ; ++i)
{
......
}

(感谢Grandyang!!!)