题目描述
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。
注意:你不能在买入股票前卖出股票。
题目链接:力扣
解题思路
使用贪心策略,假设第 i 轮进行卖出操作,买入操作价格应该在 i 之前并且价格最低。
public class Main {
public static void main(String[] args) {
int[] prices = {7, 1, 5, 3, 6, 4};
System.out.println(maxProfit(prices));
int[] prices2 = {7, 6, 4, 3, 1};
System.out.println(maxProfit(prices2));
}
public static int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int soFarMin = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
soFarMin = Math.min(soFarMin, prices[i]);
maxProfit = Math.max(maxProfit, prices[i] - soFarMin);
}
return maxProfit;
}
}
网友评论