题目描述
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).
Example1:
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.
Example2:
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.
解题思路
- 状态转移方程
// buy[i] = max(buy[i - 1],sell[i - 1] - prices[i]); // sell[i] = max(sell[i - 1], buy[i - 1] + pirces[i]);
- 直接遍历 如果后一个值比前一个值要大的话，我们其实就可以进行计算他们的差值进行累加
// 4 7 8 2 8 最大利润很明显是 （8 - 4） + （8 - 2） = 10 就因为这个式子让我想复杂了：首先要找到一个极小值4，然后找到极大值8；然后找到极小值2，然后找到极大值8；balabala……
其实换一种思路，（7 - 4) + (8 - 7) + (8 - 2) 区别在于，直接将后一个数减前一个数就好了呀，只不过如果后一个数比前一个数小的话就不考虑而已。
class Solution {
public:
int maxProfit(vector<int>& prices) {
// buy[i] = max(buy[i - 1],sell[i - 1] - prices[i]);
// sell[i] = max(sell[i - 1], buy[i - 1] + pirces[i]);
if(prices.size() == 0){
return 0;
}
/*vector<int> buy(prices.size(), 0);
vector<int> sell(prices.size(), 0);
buy[0] = -prices[0];
sell[0] = 0;
for(int i = 1; i < prices.size(); i++){
sell[i] = max(sell[i - 1], buy[i - 1] + prices[i]);
buy[i] = max(buy[i - 1],sell[i - 1] - prices[i]);
}
return sell[prices.size() - 1];*/
int res = 0;
for(int i = 1; i < prices.size(); i++){
if(prices[i] > prices[i - 1]){
res += prices[i] - prices[i - 1];
}
}
return res;
}
};
