剑指 Offer 63. 股票的最大利润 121. 买卖股票的最佳时机

本文主要是介绍剑指 Offer 63. 股票的最大利润 121. 买卖股票的最佳时机，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof
著作权归领扣网络所有。

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1:

输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 =6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1] 输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

限制：

0 <= 数组长度 <= 10^5

解答

在买卖股票时最大获益肯定是低买高买，故而用一个变量记录历史最低价格 minprice。
假设股票是在i天买的（i为最低价），则minprice=prices[i]；
那么在第j天卖出股票能得到的利润就是 prices[j] - minprice。

推演公式为：

profit[i] = max(profit[i-1], prices[i]-minprice)

示例1的过程 [7,1,5,3,6,4] 的动态规划过程：

i	prices[i]	min	prices[i] - prices[min]	profit[i]=max(profit[i-1], prices[i]-prices[min])
1	7	0	0	0
2	1	0	0	0
3	5	2	4	4
4	4	2	4	4
5	6	2	5	5
6	4	2	3	5

示例2的过程 [7,6,4,3,1] 的动态规划过程：

i	prices[i]	min	prices[i] - prices[min]	profit[i]=max(profit[i-1], prices[i]-prices[min])
1	7	0	0	0
2	6	0	0	0
3	4	0	0	0
4	3	0	0	0
5	1	0	0	0

代码

时间复杂度为 O(n)
空间复杂度为 O(1)

int maxProfit(int* prices, int pricesSize){if ( prices == NULL || pricesSize == 0 ) { //检验输入的合理性return 0;}int min = prices[0];//定义变量min保存数组中的最小值int *dp = (int *)calloc( pricesSize, sizeof(int) ); //默认初始化都为0for( int i = 1; i < pricesSize; i++ ) { //从1开始遍历if( prices[i] < min ) { //保存数组中的最小值min = prices[i];} //今日的最佳收益为昨天的最佳收益、今天股票价格减去在股票价格最低时买入价格这两者之间的最小值。dp[i] = dp[i-1] > (prices[i] - min) ? dp[i-1] : (prices[i] - min);}return dp[pricesSize-1];
}