leetcode-121：买卖股票的最佳时机

问题

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：
在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票

示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0

提示：
1 <= prices.length <= 105
0 <= prices[i] <= 104

思路

暴力

class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++){
                result = Math.max(result, prices[j] - prices[i]);
            }
        }
        return result;
    }
}

• 时间复杂度：
• 空间复杂度：

贪心

如果我是在历史最低点买的股票就好了！我们只要用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice

class Solution {
    public int maxProfit(int[] prices) {
        int miniprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            miniprice = Math.min(miniprice, prices[i]);  // 取最小价格
            maxprofit = Math.max(maxprofit, prices[i] - miniprice); 
        }
        return maxprofit;
    }
}

• 时间复杂度：

• 空间复杂度：

  动态规划

• 确定dp数组以及下标的含义

  • 因此当天是否持股是一个很重要的因素，而当前是否持股和昨天是否持股有关系，为此我们需要把是否持股 设计到状态数组中

  • 状态定义：

    • dp[i][j]：下标为 i 这一天结束的时候，手上持股状态为 j 时，我们持有的现金数
      • j = 1，表示当前不持股
      • j = 0，表示当前持股

  • dp[i][0] 表示第i天持有股票所得现金 ，本题中只能买卖一次，持有股票之后哪还有现金呢？

  • 其实一开始现金是0，那么加入第i天买入股票现金就是 -prices[i]， 这是一个负数
  • dp[i][1]表示第i天不持有股票所得现金
  • 注意这里说的是“持有”，“持有”不代表就是当天“买入”！也有可能是昨天就买入了，今天保持持有的状态

• 确定递推公式

  • 如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

    • 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
    • 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]
    • 那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

  • 如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来

    • 第i-1天不持有股票，那么保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
    • 第i天卖出股票，所得现金是按照今天股票佳价格卖出后所得现金：prices[i] + dp[i - 1][0]
    • 同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

• dp数组如何初始化

  • 由递推公式 dp[i][0] = max(dp[i - 1][0], -prices[i]);和 dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);可以看出

  • 其基础都是要从dp[0][0]和dp[0][1]推导出来

  • 那么dp[0][0]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp[0][0] = -prices[0];

  • dp[0][1]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][1] = 0;

• 确定遍历顺序

  • 从前向后遍历。

• 举例推导dp数组

  • 以示例1，输入：[7,1,5,3,6,4]为例，dp数组状态如下：

因为本题中不持有股票状态所得金钱一定比持有股票状态得到的多！

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
        }
        return Math.max(dp[len - 1][0], dp[len - 1][1]);
    }
}

• 时间复杂度：
• 空间复杂度：