Java 求解买卖股票的时机 II

• • 一、题目
  • 二、贪心算法分析
  • 三、代码
  • 四、总结
  • 五、动态规划解法

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

对于题目，第 0 天买入，第 3天卖出，利润为：prices[3]-prices[0]

可以分解为：(prices[3]-prices[2])+(prices[2]-prices[1])+(prices[1]-prices[0])

所以，我们只需要收集每天的正利润就可以，收集正利润的区间，就是股票的买卖区间，而且我们关注的是最终的利润，也不需要记录区间。

这也就是贪心所贪之处，局部最优（收集每天的正利润），达到全局最优（求得最大利润）

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        for (int i = 1; i < prices.length; i++) {
            //只要其中的正值
            res += Math.max(0, prices[i] - prices[i - 1]);
        }
        return res;
    }
}

局部最优推到全局最优

（1）确定dp 数组下标含义

（2）确定dp数组初始化

（3）确定递推公式

（4）确定遍历逻辑顺序

class Solution {
    public int maxProfit(int[] prices) {
        // dp[i][j] 表示第 i 天买或卖的最大利润
        // dp[i][0] 表示第 i 天买入股票的最大利润
        // dp[i][1] 表示第 i 天卖出股票的最大利润
        int[][] dp = new int[prices.length][2];
        // 第一天，买入股票的最大利润
        dp[0][0] = 0 - prices[0];
        // 第一天，卖出股票的最大利润
        dp[0][1] = 0;
        for (int i = 1; i < prices.length; i++) {
            // 今天买入有两种情况，取最大值：要么保持昨天买入的状态，要么昨天是卖出，今天买入
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            // 今天卖出有两种情况，取最大值：要么保持昨天卖出的状态，要么昨天是买入的状态，今天卖出
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[prices.length-1][1];
    }
}