一、題目122. 買賣股票的最佳時(shí)機(jī) II

LeetCode地址：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
難度：簡(jiǎn)單
給定一個(gè)數(shù)組 prices ，其中 prices[i] 是一支給定股票第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤(rùn)。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買前出售掉之前的股票）。

示例 1：

輸入: prices = [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 。
隨后，在第 4 天（股票價(jià)格 = 3）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 6-3 = 3 。

示例 2：

輸入: prices = [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接連購(gòu)買股票，之后再將它們賣出。因?yàn)檫@樣屬于同時(shí)參與了多筆交易，你必須在再次購(gòu)買前出售掉之前的股票。

示例 3：

輸入: prices = [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤(rùn)為 0。

提示：

1 <= prices.length <= 3 * 10⁴
0 <= prices[i] <= 10⁴

二、解題思路

一開始想到的思路是這樣的低買高賣就有利可圖，如果價(jià)格持續(xù)走高就一直持有，直到降低前或者到最后一天。

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    var len = prices.length
    var total = 0;//利潤(rùn)
    var num = -1;//不持有股票
    for(var i = 0;i < len - 1;i++){
        //如果明天有利可圖手里沒股票就買股票，否則持有股票就賣出
        if(prices[i] < prices[i+1]){
            if(num == -1){
                num = prices[i];
            }
        }else{
            if(num >= 0){
                total = total + prices[i] - num;
                num = -1;
            }
        }
        //如果是最后一天，手里還有股票就全賣了
        if( i + 2 == len && num >= 0){
            total = total + prices[i+1] - num;
            num = -1;
        }
    }
    return total;
};

來自網(wǎng)友類似的解法，地址

守財(cái)奴

ps:這種解法符合實(shí)際股票買賣過程，但是過于繁瑣，沒有體現(xiàn)貪心思想。實(shí)際上，只要今天比昨天高就賣，賺差價(jià)。
連續(xù)漲的，也是一天一賣。賣了當(dāng)天的再買今天的，明天賣有利潤(rùn)就可累積出最大利潤(rùn)。

三、實(shí)現(xiàn)過程

c++

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

PHP

class Solution {

    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $len = count($prices);
        $sum = 0;
        for($i = 1;$i < $len;$i++){
            if($prices[$i]>$prices[$i-1]){
                $sum = $sum + $prices[$i]-$prices[$i-1];
            }
        }
        return $sum;
    }
}

JavaScript

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    var len = prices.length
    var total = 0;
    for(var i = 1;i < len;i++){
        if(prices[i] > prices[i-1]){
            total = total + prices[i] - prices[i-1];
        }
    }
    return total;
};

四、小結(jié)

貪心算法無(wú)論實(shí)際過程如何，只要局部最優(yōu)就能使得全局最優(yōu)。