63.股票的最大利润

链接

​​https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/​​ 难度： #中等

题目

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？示例 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。      

限制：​

​0 <= 数组长度 <= 10^5​

​​ 注意：本题与主站 121 题相同：​​https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/​​

代码框架

class Solution {
    public int maxProfit(int[] prices) {

    }
}      

题目解析

解答思路1：

遍历数组，

分别把当前的元素作为买入时机，

把当前元素后面的元素依次作为卖出时机，

从而找到最大利润。

解答思路2：

优化暴利解法，

在寻找第i天后卖出的最佳时机，

存在重复子问题，

优化后避免的重复寻找。

遍历数组，

从第i天开始买入prices[i]，

则第i天后面的最大值prices[m]可以卖出，

取profit=Max(profit,prices[m]-prices[i]),

再计算第i+1天的买入prices[i+1],

则第i+1天后面的最大值prices[n]可以卖出,

取profit=Max(profit,prices[n]-prices[j]),

讨论两次最大值prices的下标m和n，

如果m=n,则存在重复子问题，

不需要反复计算下标的最大值，

可以极大的优化暴利解法的性能，

所以需要记录最大值所在的下标m，

可以知道第i到m-1天后面的最大值都是prices[m],

考虑数组[7,1,5,3,6,4]

对应下标[0,1,2,3,4,5]

第0到3次的最大值都是6，下标为4,

第4次由于自己本身是最大值，没有比较的必要了，

后面如果还有其他值，

可以从第m+1个元素开始递归，

重复进行上述操作，

当前最大值前面的值都不需要在考虑了，

因为无论前m-1个元素多小，

后面的最大值已经是第m个元素了，

两者的差值不可能再大了。

解答思路3：

遍历数组一遍，

在遍历第i天的时候，

找出到目前为止当前的最小值，

然后假设自己就是在那一天买的，

不需要确切知道是哪一天买的，

然后在第i天的时候，

计算卖出的利润，

保存利润的最大值，

直到数组遍历完毕，

就能获得最大的利润，

不需要确切知道是哪一天卖的。

测试用例

package edu.yuwen.sowrd.d60.num63.solution;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import edu.yuwen.sowrd.d60.num63.sol5.Solution;

public class SolutionTest {
    /**
     * 示例 1:  
    *   输入: [7,1,5,3,6,4]
    *  输出: 5
    *  解释: 在第 2 天(股票价格 = 1)的时候买入，在第 5 天(股票价格 = 6)的时候卖出，最大利润 = 6-1 = 5 。
    *  注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
     */
    @Test
    public void testCase1() {
        Solution solution = new Solution();

        int[] prices = { 7, 1, 5, 3, 6, 4 };
        int res = solution.maxProfit(prices);
        Assertions.assertEquals(5, res);
    }

    /**
     * 示例 2:
    * 输入: [7,6,4,3,1]
    * 输出: 0
    * 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
     */
    @Test
    public void testCase2() {
        Solution solution = new Solution();

        int[] prices = { 7, 6, 4, 3, 1 };
        int res = solution.maxProfit(prices);
        Assertions.assertEquals(0, res);
    }

    /**
    * 输入: [2,1,4]
    * 输出: 3
    * 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
     */
    @Test
    public void testCase3() {
        Solution solution = new Solution();

        int[] prices = { 2, 1, 4 };
        int res = solution.maxProfit(prices);
        Assertions.assertEquals(3, res);
    }
}      

解答1

package edu.yuwen.sowrd.num63.sol1;

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        // 初始化最大利润为0
        int max = 0;
        // 买入时机，最后一天无法作为买入时机
        for (int i = 0; i < prices.length - 1; i++) {

            // 卖出时机
            for (int j = i + 1; j < prices.length; j++) {
                // 找出最大利润
                int profit = prices[j] - prices[i];
                max = Math.max(max, profit);
            }
        }

        return max;
    }
}      

解答2

package edu.yuwen.sowrd.num63.sol2;

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        int profit = 0;
        int maxIndex = -1;
        // 第i天买入时机，最后一天无法买入
        for (int i = 0; i < prices.length - 1; i++) {
            // 最大值的时候，也无法买入
            if (i == maxIndex) {
                continue;
            }
            // i大于最大值的下标，则需要重新查找最大值
            if (i > maxIndex) {
                // 找到i+1到length-1的最大值的下标，左闭右开
                maxIndex = findMax(prices, i + 1);
            }
            profit = Math.max(profit, prices[maxIndex] - prices[i]);
        }

        return profit;
    }

    private int findMax(int[] prices, int i) {
        int max = Integer.MIN_VALUE;
        int maxIndex = -1;
        for (int m = i; m < prices.length; m++) {
            // 找到最大值的下标，且如果有重复的最大值，取索引最大的
            if (max <= prices[m]) {
                max = prices[m];
                maxIndex = m;
            }
        }
        return maxIndex;
    }
}      

解答3

package edu.yuwen.sowrd.num63.sol3;

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        int profit = 0;
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            // 更新最小值，且买入当天不卖出
            if (min > prices[i]) {
                min = prices[i];
                continue;
            }

            // 更新最大利润
            int newP = prices[i] - min;
            if (profit < newP) {
                profit = newP;
            }
        }
        return profit;
    }
}      

解答4 推荐

package edu.yuwen.sowrd.num63.sol4;

public class Solution {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for (int price : prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }

}      

解答5

package edu.yuwen.sowrd.num63.sol5;

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        int[] dp = new int[prices.length];
        // 当天买入卖出利润0
        dp[0] = 0;
        // 前i天的最小值
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            // 更新最小值
            min = Math.min(min, prices[i]);
            // 当天卖出的最大利润
            int profit = prices[i] - min;
            // 前i天买卖一次的最大利润
            dp[i] = Math.max(dp[i - 1], profit);
        }

        return dp[prices.length - 1];
    }
}