买卖股票的最佳时机

难度:

标签:

题目描述

给定一个数组 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 <= 10⁵
0 <= prices[i] <= 10⁴

代码结果

运行时间: 792 ms, 内存: 29.5 MB

/*
 * 思路：
 * 使用Java Streams API来实现相同的逻辑。
 * 通过将prices数组转为IntStream，然后使用reduce方法来完成单次遍历。
 * 维护两个数组：minPrice和maxProfit，分别用于保存迄今为止的最小价格和最大利润。
 */
import java.util.stream.IntStream;
 
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int[] result = IntStream.of(prices)
                .reduce(new int[]{Integer.MAX_VALUE, 0}, (acc, price) -> {
                    acc[0] = Math.min(acc[0], price);
                    acc[1] = Math.max(acc[1], price - acc[0]);
                    return acc;
                }, (acc1, acc2) -> acc1);
        return result[1];
    }
}

解释

方法:

这个题解使用了动态规划的方法。它维护了一个二维的 dp 数组，其中 dp[i][0] 表示第 i 天结束时不持有股票的最大利润，dp[i][1] 表示第 i 天结束时持有股票的最大利润。对于每一天，我们有两种选择：1. 不持有股票，此时最大利润为前一天不持有股票的利润和前一天持有股票然后今天卖出的利润中的较大值；2. 持有股票，此时最大利润为前一天持有股票的利润和前一天不持有股票然后今天买入的利润中的较大值。最终的结果是最后一天不持有股票的最大利润。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

为什么在动态规划中使用了一个额外的天数（n+1天）来初始化dp数组，而实际问题中只有n天？

▷

在动态规划中使用一个额外的天数（n+1天）来初始化dp数组，是为了方便处理边界条件，使得数组索引与天数对应起来。这种方法使得dp[1]到dp[n]直接对应第1天到第n天的情况，而dp[0]可以用来表示初始状态，即在开始交易前的状态。这样做可以使逻辑更清晰，代码更易于理解和维护。

🦆

在dp数组中，dp[0][1]被设置为负无穷，这是基于什么考虑？

▷

dp[0][1]被设置为负无穷是因为这代表在交易开始前，即第0天时，已经持有股票的状态。这种状态是不可能的，因为在交易开始前我们是不可能持有股票的。设置为负无穷可以确保在动态规划过程中，任何基于这种不可能状态的决策都会被排除，因为与负无穷比较的任何正常值都会更优。

🦆

动态规划解法中，对于'不持有股票'的状态转移方程 dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i-1])，为什么要将前一天持有股票并在今天卖出的情况加上prices[i-1]？

▷

在状态转移方程dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1])中，dp[i-1][1] + prices[i-1]表示的是前一天持有股票，并在第i天（即prices数组中的第i-1个元素）卖出股票的情况。由于卖出股票会获得收益，因此需要将股票的售价prices[i-1]加到前一天持有股票的最大利润dp[i-1][1]上，以计算出在第i天不持有股票时可能达到的最大利润。

🦆

在计算持有股票的最大利润时，dp[i][1] = max(dp[i-1][1], -prices[i-1])中为什么选择在第i天买入股票时直接使用-prices[i-1]而不是dp[i-1][0]-prices[i-1]？

▷

在状态转移方程dp[i][1] = max(dp[i-1][1], -prices[i-1])中，-prices[i-1]表示在第i天买入股票的成本，而这里不使用dp[i-1][0] - prices[i-1]是因为dp[i-1][0]表示前一天不持有股票的最大利润，如果在第i天买入股票，那么这天的操作是独立的，不应该从之前的利润中减去股票的价格。这样可以确保买入操作只考虑当天的价格，而不是受到前一天不持股状态的影响。这种简化假设是基于问题的模型，其中每次买入都是新的独立操作，只需考虑当天的成本。

相关问题

最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。