買賣股票的最佳時機

題目：給定一個數(shù)組 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數(shù)組初始化：dp[0][0] = 0，dp[0][1] = -prices[0]
• 遍歷順序：從小到大
• 打印dp數(shù)組

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;
        // 持有股票，就要買入股票，利潤肯定暫時是負數(shù)
        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];
    }
}

通過遞推公式可以發(fā)現(xiàn)，當前第i天的是否持有股票只是和前一天有關系，所有我們可以使用兩個變量來存儲

class Solution {
    public int maxProfit(int[] prices) {
        // 初始化
        // 第0天不持有股票
        int dp_i_0 = 0;
        // 第0天持有股票
        int dp_i_1 = -prices[0];
        // 因為當前的天是否持有股票只和相鄰的天有關系，所有我們可以采用兩個變量存儲，類似斐波那契數(shù)列的空間復雜度為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;
    }
}

買賣股票的最佳時機Ⅱ

題目：給你一個整數(shù)數(shù)組 prices ，其中 prices[i] 表示某支股票第 i 天的價格。

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

返回 你能獲得的 最大 利潤 。

思路：和買賣股票1的區(qū)別就是買賣股票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];
    }
}

空間優(yōu)化文章來源地址http://www.zghlxwxcb.cn/news/detail-425618.html

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已經(jīng)發(fā)生變化了，所有使用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;
    }
}

到了這里，關于算法刷題｜121.買賣股票的最佳時機、122.買賣股票的最佳時機Ⅱ的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！