122. 买卖股票的最佳时机 II - 力扣（LeetCode） (leetcode-cn.com)

难度：中等
题目描述：给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

分析

贪心.png

dp.png

此题是121题的进阶， 
121题实质计算的是一次交易的最大利润，而122题不限制交易次数，计算的是总体最大利润 
此题有两种解题思路 
1- 使用贪心算法 
对于本题来说使用贪心算法，将数组中局部最优解相加，最后构成全局最优解 
例如：数组[7,1,5,3,6,4],一次交易的全局最优解可以通过121题可知 
而局部最优解为[1,5] 和 [3.6] 可以通过图看出，这都是单调递增区间，将两次交易利润相加就是全局最优解 
2- 使用动态规划 
由于题目中提到不能同时参与多笔交易，所以每天存在两种状态，一种是手里有一只股票，一种是手中没有股票 
所以可以根据交易状态确定dp数组 
dp[i][j]表示第i天，交易状态为j的最大利润，此处i为数组长度，j为状态值即0，1 
dp数组如图所示 
举个简单的例子： 
初始资金为100 
第一天股票价格为7，即prices[0]=7 
此时有两个选择，1持有股票，2不持有，对应dp数组中的j下标 
如果此时不持有股票，表示我们并没有购买，所以此时利润为0，即dp[0][0]=0 
如果此时持有股票，表示我们花7元买了一股，此时利润为-7，即dp[0][1]=-7 
此时dp数组进行初始化完成，但后续需要找到特定表达式，计算当前最佳利润 
第二天股票价格为1，即prices[1]=1 
如果此时选择不持有股票，这时有两种情况， 
第一，昨天不持有股票，今天也不持有股票，则我们本金并没有变化，即利润为0； 
第二，昨天持有股票，今天不持有股票，表示我们昨天花7元买了股票，剩余本金93元，今天股价1元，我们卖出，则本金94元，即利润为-6。 
由于我们需要计算当前选择的利润最大值，所以我们取两个选择的最大值为今日选择不持有股票的最大利润，即dp[1][0] = max(dp[0][0],dp[0][1]+prices[1]) = 0 
如果此时选择持有股票，也存在两种情况 
第一，昨天不持有股票，今天持有股票，表示我们今天花1元购买一股，即利润为-1； 
第二，昨天持有股票，今天继续持有股票，依然是昨天7元一股买的股票，由于股票跌了在没有卖出之前并不影响自己本身的利润，所以利润依旧是-7 
由于我们需要计算当前选择的利润最大值，所以我们取两个选择的最大值为今日选择不持有股票的最大利润，即dp[1][1] = max(dp[0][0]-prices[1],dp[0][1]) = -1 
第三天股票价格为5，即prices[2]=5 
根据第二天推理可得 
dp[2][0] = 4 
dp[2][1] = -1 
所以最后dp数组如图所示

解题

贪心

class Solution {
        public int maxProfit(int[] prices) {
            if (prices == null || prices.length <= 1) return 0;

            int ans = 0;
            for (int i = 1; i < prices.length; i++) {
                if (prices[i] > prices[i-1]) {  // 卖出有利可图
                    ans += (prices[i] - prices[i-1]);
                }
            }

            return ans;
        }
    }

动态规划

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]);
                dp[i][1] = Math.max(dp[i-1][0] - prices[i], dp[i-1][1]);
                System.out.println(dp[i][0] + " " + dp[i][1]);
            }
            return dp[prices.length-1][0];
        }
    }