股票的最大利润（java算法题，动态规划法的应用）
一、题目：假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
二、示例 :
输入: [7,1,5,3,6,3] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。如果价格一直在降，最大利润可以是0。
三、代码：
public int maxProfit(int[] prices) {
if(prices==null || prices.length <= 1){
return 0;
}
int profit = 0;
int min = prices[0];
for(int i = 1;i<prices.length;i++){
if(min>prices[i]){
min = prices[i];
}else{
profit = Math.max(profit,prices[i]-min);
}
}
return profit;
}
四、分析：
- 设利润profit初值为0，min为遍历过程中的最小值。
- 如果min>prices[i]，说明当前min不是最小的，更新min。
- 如果min<=prices[i]，说明当前的min是最小的，用当前价格减去min，得利润差（只有当前价格大于之前遍历中的最小值，才有利润）。拿所得结果与之前存储的最大利润作比较，取最大值。
- 此题是典型的动态规划法的应用。
