买卖股票的最佳时机

题目：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

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

• dp[i][0]表示第i天不持有股票的最大利润；dp[i][1]表示第i天持有股票的最大利润
• 递推公式
  • 第i天不持有股票：dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]
    • 昨天本来就不持有：dp[i-1][0]
    • 昨天持有，但是今天买了，所有今天也就不持有了：dp[i-1][1]+prices[i]
  • 第i天持有股票：dp[i][1] = Math.max(dp[i-1][1],0-prices[i])
    • 昨天本来就持有：dp[i-1][1]
    • 昨天本来没有，今天买了，就持有了，因为只能买卖一次，所有买的时候手里的利润一定是0：0-prices[i])
• dp数组初始化：dp[0][0] = 0，dp[0][1] = -prices[0]
• 遍历顺序：从小到大
• 打印dp数组

class Solution {
    public int maxProfit(int[] prices) {
        // dp[i][0]表示第i天不持有股票的最大利润，dp[i][1]表示第i天持有股票的最大利润
        int[][] dp = new int[prices.length][2];
        // 初始化
        dp[0][0] = 0;
        // 持有股票，就要买入股票，利润肯定暂时是负数
        dp[0][1] = -prices[0];
        for(int i = 1;i<prices.length;i++){
            // 第i天不持有股票
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            // 第i天持有股票
            dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
        }
        return dp[prices.length - 1][0];
    }
}

通过递归公式可以发现，当前第i天的是否持有股票只是和前一天有关系，所有我们可以使用两个变量来存储

class Solution {
    public int maxProfit(int[] prices) {
        // 初始化
        // 第0天不持有股票
        int dp_i_0 = 0;
        // 第0天持有股票
        int dp_i_1 = -prices[0];
        // 因为当前的天是否持有股票只和相邻的天有关系，所有我们可以采用两个变量存储，类似斐波那契数列的空间复杂度为O(1)的处理
        for(int i = 1;i<prices.length;i++){
            dp_i_0 = Math.max(dp_i_0,dp_i_1+prices[i]);
            dp_i_1 = Math.max(dp_i_1,-prices[i]);
        }
        return dp_i_0;
    }
}

买卖股票的最佳时机Ⅱ

题目：给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

思路：和买卖股票1的区别就是买卖股票1买入的时候手里的利润一定是0，而本题可以多次买入所有买入股票的时候手里的利润就不一定是0

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for(int i = 1;i<prices.length;i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
            // 因为可以多次买卖股票，所有这里手里的利润就不一定是0了，所以最大金额就要使用之前的利润减轻今天的股票价格
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] - prices[i]);
        }
        return dp[prices.length - 1][0];
    }
}

空间优化

class Solution {
    public int maxProfit(int[] prices) {
        int dp_i_0 = 0;
        int dp_i_1 = -prices[0];
        for(int i = 1;i<prices.length;i++){
            // 因为先计算的dp_i_0，所有计算dp_i_1的时候dp_i_0已经发生变化了，所有使用temp记录一下值
            int temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0,dp_i_1+prices[i]);
            dp_i_1 = Math.max(dp_i_1,temp-prices[i]);
        }
        return dp_i_0;
    }
}