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

解析

此题是买股票，即低买高卖，那怎么才能达到最大的利润呢，即尽可能的多进行买入卖出，这样才能到达最大的利润。只要今天比昨天的高，那就昨天买今天卖。这个就是典型的“贪心思想”。

代码

int maxProfit2(int* prices, int pricesSize) {
    if (prices == NULL || pricesSize < 2)
        return 0;
    
    int maxProfit = 0;
    
    for (int i = 0; i < pricesSize - 1; ++i) {
        int currentProfit = prices[i + 1] - prices[i];
        
        if (currentProfit > 0)
            maxProfit += currentProfit;
    }
    
    return maxProfit;
}