给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
暴力解法：因为只能买卖一次，故可依次循环，找到最优解即可
实现代码：
/**
* 买卖股票的最佳时机：只能买卖一次
* 暴力解法
* 【例子】:[7,1,5,3,6,4]
* @param prices
* @return
*/
public static int maxProfit_violence(int[] prices) {
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
for (int j = i+1; j < prices.length; j++) {
if (prices[j] - prices[i] > maxProfit) {
maxProfit = prices[j] - prices[i];
}
}
}
return maxProfit;
}
动态规划解法：解题思路：
s1: 记录今天之前买入的最小值
s2: 计算今天卖出的最大获利
s3: 比较每天的最大获利
代码：
/**
* 买卖股票的最佳时机：只能买卖一次
* 动态规划解决
* 【例子】:[7,1,5,3,6,4]
*
* 解题思路：
* s1: 记录今天之前买入的最小值
* s2: 计算今天卖出的最大获利
* s3: 比较每天的最大获利
*
* @param prices
* @return
*/
public static int maxProfit_dynamic(int[] prices) {
if (prices.length <= 1) {
return 0;
}
int maxProfit = 0;
int min = prices[0];
for (int i = 0; i < prices.length; i++) {
maxProfit = Math.max(maxProfit, prices[i] - min);
min = Math.min(min, prices[i]);
}
return maxProfit;
}
