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

import java.util.*;

//该题与打家劫舍类似，可以通过考虑当天持股还是不持股，来分别考虑
public class Solution {
   //dp[i][0] 表示在第i天不持股的最大收益
   //dp[i][1]表示在i天持股的最大收益
    public int maxProfit (int[] prices) {
        // 多次买入卖出，再次买入前先卖出
        int n = prices.length;
        int[][] dp = new int[n][2];
        //1.初始化
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        //1.当天不持股可能是当天卖出了股票或者是之前卖出了股票
        //2.当天持股可能是前几天买的还没卖出，或者是当天买入

        //2.填表 ,1.当天持股时此时最大收益为前一天持股还是前一天不持股的最大值
        //2.当天不持股时，此时为前一天持股还是不持股的最大收益
        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 Math.max(dp[n-1][0],dp[n-1][1]);
    }
}