If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
解题思路:
动态规划: 局部最优 以及 全局最优
要获得最大收益,最理想的状态就是:在最低价买进,最高价卖出。
在第 i 天卖出最大收益 profit[i] = price[i] - minPrice。
在0...n中的最大收益就为 max(profit[0..n])
在这个过程中最主要的就是要track出第i天的最小价格
java code:
public int maxProfit(int[] prices) { int maxProfit = 0; int minPrice = Integer.MAX_VALUE; for(int i = 0; i < prices.length; i++){ minPrice = minPrice < prices[i]? minPrice : prices[i]; int profit = prices[i] - minPrice; maxProfit = maxProfit > profit ? maxProfit : profit; } return maxProfit; }
No comments:
Post a Comment