问题描述
假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?
- 示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
- 示例 2:
‘’输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。’’
问题分析
对于股票在当前可以买入也可以卖出,并且当前给定的是一个股票涨幅表,只是希望通过这个数组来计算出可能获取的最大利润,其实变换一个问题就是给定数组,计算出该数组能获取的最大差值(限定条件data[j] < data[i])
这个问题是一个比较典型的动态规划的问题,那么我们就是要找到动态规划方程;
对于第i天卖掉股票的最大利润可以表示为:
dp(i),那么当前股票的收益是前一天的收益dp(i-1)与当前股票价格与前面最便宜的股票价格之差,那个收益更大;
主要的方程为:
dp(0)=0
dp(i) = max(dp(i-1), price - minPrice);
代码实现
class Solution {
public int maxProfit(int[] prices) {
if(prices == null || prices.length == 0){
return 0;
}
int cost = Integer.MAX_VALUE, price = 0;
int maxProfit = 0;
for(int j=0; j<prices.length; j++){
//存储前面买取股票的最小值
cost = Math.min(cost, prices[j]);
//计算获取的最大利润
maxProfit = Math.max(maxProfit, prices[j] - cost);
}
return maxProfit;
}
}
思路扩展
上面问题分析的可知,主要是在数组中找到数组的最大值和最小值,并且要求这个最大值在最小值的右侧;
可以申明变量maxIndex代表最大值的位置,minIndex为最小值的位置;