1. 股票的最大利润

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

  1. 示例 1:
  3. 输入: [7,1,5,3,6,4]
  4. 输出: 5
  5. 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
  6.      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
  7. 示例 2:
  9. 输入: [7,6,4,3,1]
  10. 输出: 0
  11. 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

思路：

需要保证的条件：

  • 卖出的价格对应的元素索引必须在买进的价格之后
  • 最小值买进可能并不是最优结果（例如：[2,4,1]，1买进，利润为0）

解决：

  • 在进行数组便利的时候，当买进价格变更，则卖出价格也随之改变，保证卖出在买进后。
  • 上述条件的第二条，由于只需要进行得到最大利润，无需关心买入值和卖出值，因此可在每次进行遍历后求取一次利润。
class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==0){
            return 0;
        }
        int min = prices[0];
        int max = prices[0];
        int res = 0;
        for(int price : prices){
            if(price<min){  
                min = price;
                max = price;
            }
            if(price>max){
                max = price;
            }
            if((max - min)>res ){
                res = max - min;
            }
        }
        return res;
    }
}

上述代码可优化：使用java的内置的Math函数。

class Solution {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE,profit=0;
        for(int price : prices){
            cost = Math.min(price,cost);
            profit = Math.max(profit,price-cost);
        }
        return profit;
    }
}
  • 这里不断更新花费金额，并且每次都求取一次利润，保证了卖出一定在买进之后。
  • 但实际在遍历数组时，cost和profit是必须进行更新（比较之后完成赋值），而实际情况判断条件了之后可以进行跳过，减少时间消耗。