LeetCode: Best Time to Buy and Sell Stock II

Say you have an array for which the i^th 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).

---

To make the maximum profit, we can do it greedily. When the price is increasing, we hold. When the price is decreasing, we watch.

C++ Code:

/* 
 * func: maximum_profit
 * goal: find the maximum profit if we can complete as many transaction as possible
 * @param prices: daily price of the stock
 * return: maximum profit
 */
/*
 * Do it greedily.
 * complexity: time O(n), space O(1)
 */
int maximum_profit(vector<int> &prices){
    int max_profit = 0;
    for(int i=1; i<prices.size(); ++i){
        //If price is increasing, we hold
        if(prices[i] >= prices[i-1]){
            max_profit += prices[i] - prices[i-1];
        }
    }
    return max_profit;
}

Python Code:

# func: find the maximum profits if we can complete multiple transactions
# @param prices: daily price of the stock
# @return: maximum price
# complexity: time O(n), space O(1)
def maximum_profit(prices):
    max_profit = 0
    for i in xrange(1, len(prices)):
        if prices[i] >= prices[i-1]:
            max_profit += prices[i] - prices[i-1]
    return max_profit