买卖股票当中的最佳时机

题目

给定一个数组$ prices $，它的第 $i $个元素 \(prices[i]\) 表示一支给定股票第 $i $天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

解法

暴力解法

class Solution {public int maxProfit(int[] prices) {int n=prices.length;int res=0;for(int i=0;i<n;i++){int cur=prices[i];int k=i+1;while(k<n&&prices[k]>cur){res=Math.max(prices[k]-cur,res);k++;}}return res;}
}

动态规划

class Solution {public int maxProfit(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;}
}

动态规划状态定义

\(dp[i]\)表示从第 0天到第\(i\)天，完成一轮买卖操作（买入 + 卖出）能获得的最大收益。
状态转移方程:$$dp[i]=max(dp[i−1], prices[i]−low)$$

\[low=min(prices[0],prices[1],…,prices[i−1]) \]