122. Best Time to Buy and Sell Stock II
Say you have an array for which the ith 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 (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
加一个示例：
Input:[6,1,2,3,4,5,7]
Output:6
解题思路
最开始是这样考虑的：从当前这一天往后遍历，找到一个峰值（左右两天的价格都比它低）或者到达向量尾部，则从这一天卖掉。但这样有时候只能找到局部最优解，而非全局最优解，如我额外加上的例子（按这个思路，output为1）。考虑题目中强调的不能在同一天买和卖，其实如果在同一天先卖、再买，实质上是没有获利，全局获利不会受影响。基于贪心的想法，只要明天比今天价格高，我就买，保证一定可以获利。明天卖掉，保证这部分利益获得，再买入。第三天的价格如果更好，第三天再卖到（相当于今天买，第三天卖），如果第三天的价格不好，明天就不会买入。
代码如下：
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() <= 1) {
return 0;
}
int res = 0;
for(int i = 0; i < prices.size() - 1; i++) {
if(prices[i] < prices[i+1]) {
res += prices[i+1] - prices[i];
}
}
return res;
}
};