题目
题目链接
https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/
解题思路
题解
动态规划
- 利润计算:加入第 a 天买入,第 b 天卖出,利润为 prices[b] - price[a],且 b > a
- 此时假设,第 a 天的价格是这几天中最低的,且假设第 b 天为这几天中最高价,此时 prices[b] - price[a] 就为最大利润
- 此时在 2 的基础上,假如今天是第 c 天,此时最大利润:Math.max(price[c], price[b] - price[a])
代码
class Solution {
public int maxProfit(int[] prices) {
// 最大利润
int maxProfit = 0;
// 最小价格
int minPrice = 0;
for (int i = 0; i < prices.length; i++) {
// 刚开始不存在所谓的利润,此时第一日就为最小价格
if (i == 0) {
minPrice = prices[i];
continue;
}
// 今天加个比最小的还小,替换最小值
if (prices[i] < minPrice) {
minPrice = prices[i];
continue;
}
// 最大利润:今天加个 - 最小价格 与 已经计算过的最大差价比较,去更大的那个
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
}
return maxProfit;
}
}