63.股票的最大利润

raylan.chen大约 2 分钟

使用 dp[i] 记录今天卖出芯片所能获取的最大利润，

dp[i] = max（今天的售价 - 昨天的售价，今天的售价 - 昨天的售价 + 前 i - 1 天获得的最大利润）

今天的售价 - 昨天的售价：代表昨天购入

今天的售价 - 昨天的售价 + 前 i - 1 天获得的最大利润：代表昨天之前已购入

prices	8	12	15	7	3	10
prices[i] - prices[i - 1]	0	4	3	-8	-4	7
dp[i]	0	4	7	-1	-4	7

class Solution {
    public int bestTiming(int[] prices) {
        // dp[i] 今天卖出芯片能获得的最大利润
        // dp[i] = max(prices[i] - prices[i - 1], prices[i] - prices[i - 1] + dp[i - 1])
        if (prices == null || prices.length == 0) return 0;
        int[] dp = new int[prices.length];
        dp[0] = 0;
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            dp[i] = Math.max(prices[i] - prices[i - 1], prices[i] - prices[i - 1] + dp[i - 1]);
            max = Math.max(dp[i], max);
        }
        return max;
    }
}

优秀题解

C++ 版本

/*******************************************************************
Copyright(c) 2016, Harry He
All rights reserved.

Distributed under the BSD license.
(See accompanying file LICENSE.txt at
https://github.com/zhedahht/CodingInterviewChinese2/blob/master/LICENSE.txt)
*******************************************************************/

//==================================================================
// 《剑指Offer——名企面试官精讲典型编程题》代码
// 作者：何海涛
//==================================================================

int MaxDiff(const int* numbers, unsigned length)
{
    if(numbers == nullptr && length < 2)
        return 0;

    int min = numbers[0];
    int maxDiff = numbers[1] - min;

    for(int i = 2; i < length; ++i)
    {
        if(numbers[i - 1] < min)
            min = numbers[i - 1];

        int currentDiff = numbers[i] - min;
        if(currentDiff > maxDiff)
            maxDiff = currentDiff;
    }

    return maxDiff;
}

使用 min 保存前 i - 1个数字中的最小花费，

随后使用 numbers[i] - 前 i - 1 个数字中的最小花费，来寻找最大利润，简单、直接、高效！

Java 版本

class Solution {
    public int bestTiming(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for(int price : prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/gu-piao-de-zui-da-li-run-lcof/solutions/192221/mian-shi-ti-63-gu-piao-de-zui-da-li-run-dong-tai-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

63.股票的最大利润

63.股票的最大利润

参考链接

个人尝试

优秀题解