Leetcode 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 (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).

和121一样的题意，允许多次买卖，同时只能持有一支股。

最开始往DP上想的，没什么好想法，

突然想到其实只要把所有的连续上升子串的的两个端点找到就好了，

下降的不用管，因为你总是可以在下降前卖出，同时下降的最低点必然是上升的第一个点或最后一个点。

然后又想到，其实连续子串也可以拆分称相邻的上升点对，在上升子串上买卖一次和每个相邻点对都买卖是一样的效果，

于是就可以用贪心搞出来了，实现意义相当于每天都在买卖，只不过赔本的当天买进就卖出了，赚钱的留到第二天再卖。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;
        int res=0,pre=prices[0];
        for(int i=0;i<prices.size()-1;i++)
        {
            if(prices[i+1]>prices[i]) res+=prices[i+1]-prices[i];
            pre=prices[i+1];
        }
        return res;
    }
};