[LeetCode] 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).

解题思路

与版本1的题目相比，本题的区别在于允许多次交易，因此最大收益等于每对极大值与极小值的差值之和（每次在极小值点买入，极大值点卖出）。
首先将买入价格设定为prices[0]，然后遍历数组，如果当前元素的值大于等于下一个元素（该元素为极大值点），则将该元素的值与买入价格的差值加到总收益中，同时，将买入价格设置为该元素的下一个元素（在价格跌落时，当前元素值与买入价格之差为0）。

实现代码1

/*****************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/17 23:18
    *  @Status   : Accepted
    *  @Runtime  : 16 ms
******************************************************************/
#include <iostream>
#include <vector>

using namespace std;

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

        return max_global;
    }
};

实现代码2

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

        int max_global = 0;
        for (int i = 0; i < prices.size() - 1; i++)
        {
            max_global = max(max_global, max_global + prices[i + 1] - prices[i]);
        }

        return max_global;
    }
};