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

解决方法

可以进行多次的买入和卖出，那么每一次可以盈利的买卖我们都不可以放过。从图中来看的话，最大利润就是每一次涨幅的叠加。

Approach 1：Peak Valley Approach

把例子1的数据用折线图展示如下：

通过图片可以发现，利润就是一系列的峰顶和谷底的差值之和。我需要考虑每个有紧跟着谷底的顶峰，从而使利润最大化，反之如果我们没错过一次顶峰就会损失一部分利润。使用一个while循环，每次找到一个谷底的顶峰，求一次局部利润

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n == 0)
            return 0;
        int valley = prices[0];
        int peak = prices[0];
        int i = 0;
        int maxProfit = 0;
        while(i < n-1)
        {
            while(i < n-1 && prices[i] >= prices[i+1])
                i++;
            valley = prices[i];

            while(i < n-1 && prices[i] <= prices[i+1])
                i++;
            peak = prices[i];

            maxProfit += peak - valley;
        }

        return maxProfit;
    }
};

分析：
时间复杂度：O(N)
空间复杂度：O(1)

Approach 2：Simple One Pass

其实每个顶峰和谷底之间的差值也等于从谷底到顶峰的每一步的差值之和。

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

分析：
时间复杂度：O(N)
空间复杂度：O(1)

Approach 1: Brute Force

遍历所有可能的交易情况

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        return calculate(prices,0);
    }
public:
    int calculate(vector<int>& prices, int s){
        if(s >= prices.size())
            return 0;

        int max = 0;
        for(int start = s; start < prices.size(); start++)
        {
            int maxProfit = 0;
            for(int i = start + 1; i < prices.size(); i++)
            {
                if( prices[start] < prices[i])
                {
                    int profit = calculate(prices,i + 1) + prices[i] -prices[start];

                    if(profit > maxProfit)
                        maxProfit = profit;
                }
            }
            if(maxProfit > max)
                max = maxProfit;
        }
        return max;
    }
};

分析：
时间复杂度: O(n^{n)；递归函数被调用的次数为n}n

空间复杂度 : O(n)；递归的深度为n

blogs record our growth