题目描述

假设你有一个数组，其中第i个元素表示第i天某个股票的价格。

设计一种算法以找到最大利润，可以完成任意多次交易，但必须先购买股票再出售股票，不能同时多次交易。

样例

Example 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 第二天买(price = 1)，第三天卖(price=5)，利润为4;
第四天买(price = 3)，第五天卖(price=6)，利润为3。

Example 2:

输入: [1,2,3,4,5]
输出: 4
解释: 第一天买(price = 1)，第五天卖(price=5)，利润为4。

Example 3:

输入: [7,6,4,3,1]
输出: 0
解释: 这个例子中没有完成交易。

算法 贪心算法

Time $O(n)$, Space $O(1)$

遍历一次数组，低进高出，把正的价格差相加起来就是最终利润。

可以拆分成以下几种情况，

• 递增，如[1,2,3]，那么1买3卖 与 每天都买入卖出 等价
• 递减，如[3,2,1]，赚钱是赚不了的
• 先高再低，如[1,3,2]，那么只能在1买3卖捞一笔
• 先低再高，如[2,1,3]，那么同样只能在1买3卖捞一笔

短数组的情况可以推广到所有数组。

C++ 代码

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