问题描述

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

  • 示例 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)；

代码实现

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         if(prices == null || prices.length == 0){
  4.             return 0;
  5.         }
  6.         int cost = Integer.MAX_VALUE, price = 0;
  7.         int maxProfit = 0;
  8.         for(int j=0; j<prices.length; j++){
  9.             //存储前面买取股票的最小值
  10.             cost = Math.min(cost, prices[j]);
  11.             //计算获取的最大利润
  12.             maxProfit = Math.max(maxProfit, prices[j] - cost);
  13.         }
  14.         return maxProfit;
  15.     }
  16. }

思路扩展

上面问题分析的可知，主要是在数组中找到数组的最大值和最小值，并且要求这个最大值在最小值的右侧；
可以申明变量maxIndex代表最大值的位置，minIndex为最小值的位置；