题解 | #买卖股票的最好时机(二)#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    /**
       思路：
       与1相同：创建二维dp[i][0] 和 dp[i][1] 分别表示当天1是否持有股票

       与1不同的是 1只能买入卖出一次 因此求的是买入时的最低值  然后卖出时的最高值

       而本题是可以多次买入卖出，因此 dp[i][1] 不再是 求出历史最低价
                               而是判断 当前已买入的股票是否合适卖出
                       即比较 dp[i-1][1] ,dp[i-1][0]-prices[i] 哪个更大
               dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i])

     */
    public int maxProfit (int[] prices) {
        // write code here
        int n = prices.length;
        //dp[i][0]表示某一天不持股到该天为止的最大收益，dp[i][1]表示某天持股，到该天为止的最大收益
        int[][] dp = new int[n][2];
        //第一天不持股，总收益为0
        dp[0][0] = 0;
        //第一天持股，总收益为减去该天的股价
        dp[0][1] = -prices[0];
        //遍历后续每天，状态转移
        for (int i = 1; i < n; 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[n - 1][0];

    }
}