题解 | #买卖股票的最好时机(一)#
买卖股票的最好时机(一)
http://www.nowcoder.com/practice/64b4262d4e6d4f6181cd45446a5821ec
- 假设每天都会卖出股票，使用dp[ ]来记录每天的最大利润；则dp[i] = prices[i]-买入价格
- 那什么时候买入(才能让利润最大化)呢？ 使用一个min来记录买入股票价格 (默认初始化min=prices[0])
- 若当天的股票价格<min， 则min=prices[i] 即：当天买入,当天卖出--->dp[i] = 0
- 若当天的股票价格>=min，则使用之前买入的价格,当天卖出-->dp[i] = prices[i]-min
- 返回dp[i]中的最大的那个就行了。
买卖股票的最好时机
我们需要选择一天买入，选择一天卖出。最后使我们的收益最大化
XX 1.遍历每一天的最大利益情况
O(n^2),遍历每一个位置,并遍历前面的所有位置,求出最大差值
得到每个位置的最大利润
2.假设每一天都尝试卖出,返回利润最大的那一天
用一个dp数组记录每一天的最大利润, 用一个min记录(从第一天到当天)的最小股票价格
第一天利润 为0 （min初始化为第一天的股票价格, price[0]-min=0）
第二天利润 若股票价格<min,则维护min，且利润为0(买入min,又卖出price[1])
若股票价格>min,说明之前有更低的股票价格, 利润=price[1]-min
每一天都先 维护min, 然后记录利润
*/
public int maxProfit (int[] prices) {
int min = prices[0]; //记录一个最小股票价格
int[] dp = new int[prices.length]; //dp记录每一天的最大利润
int max=0;
for(int i=0;i<prices.length;i++){
if(prices[i]<min){
min = prices[i]; //维护最小股票价格
}
dp[i] = prices[i]-min; //记录当天的最大利润
max = Math.max(max,dp[i]);
}
return max;
}
投递萤石等公司10个岗位
查看18道真题和解析