剑指 Offer 63. 股票的最大利润
一、题目描述
假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?
示例 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
二、保姆级参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
class Solution {
public int maxProfit(int[] prices) {
// 边界判断,如果交易日为 0 天,那么没得交易,返回 0
// 如果交易日为 1 天,只能当天买当天卖,利润为 0
if( prices.length < 2 ) return 0;
// 设置 dp 数组,用来存放每天的最大利润
// dp[i] 表示以 prices[i] 为结尾的最大利润
// dp[0] 表示以 prices[0] 为结尾的最大利润
// dp[1] 表示以 prices[1] 为结尾的最大利润
int[] dp = new int[prices.length];
// dp[0] 表示以 prices[0] 为结尾的最大利润
// 由于只有一个交易日,只能当天买当天卖,利润为 0
dp[0] = 0;
// 初始化变量 buy,表示在哪一天购买股票
// 一开始在第 0 天购买
int buy = prices[0];
// 通过 for 循环,填充 dp
for(int i = 1 ; i < prices.length ; i++){
// 获取此时的股票价格
int sell = prices[i];
// 如果在这一天卖出去,那么利润就是当天的股票价格减去之前的购买价格
int profit = sell - buy;
// 对比一下,哪个利润更大
dp[i] = Math.max(dp[ i - 1] ,profit);
// 更新变量 buy,让 buy 为当前区间里的最小值
buy = Math.min(buy,prices[i]);
}
// 返回 dp 的最后一个结果就行
return dp[prices.length - 1];
}
}