剑指 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];
}
}
