Leetcode day2 初级算法-数组-买卖股票的最佳时机——贪心算法
题目给定一个数组 prices ,其中 prices[i] 是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。代码class Solution {public:int maxProfit(vector<int>& prices) {if(p
·
题目
给定一个数组 prices ,其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()<2) return 0;
int profit = 0;
for(int i=0;i<prices.size()-1;i++){
if(prices[i+1]-prices[i]>0) profit += prices[i+1]-prices[i];
}
return profit;
}
};
思路
贪心算法:在对问题求解时,总是做出在当前看来是最好的选择。
也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解
那么这道题使用贪心算法也是最容易解决的,
只要是上涨的我们就要计算他们的差值进行累加,不需要再找开始上涨的最小值和最大值。
为什么呢?
比如a<b<c<d,因为从a到d一直是上涨的,那么最大值和最小值的差值就是d-a,
也可以写成(b-a)+(c-b)+(d-c) = d-a
比如说prices = [1,2,3,4,5] 你会想要用 5-1 = 4啊,我要找到最大值再卖
事实上你会发现 (2-1)+(3-2)+(4-3)+(5-4) = 1+1+1+1 = 4
所以我们只需要判断数组的下一项是不是比当前项大即可 只要差值为正,我就算作profit
更多推荐
所有评论(0)