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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
        
        int n = in.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n;i++){
            nums[i] = in.nextInt();
        }
        System.out.println(run(n,nums));
}
    public static int run (int n ,int[] nums){
        if(n == 0 || n == 1){
            return 0;
        }
        /** 两次买卖对应五种状态
          0     1    2   3     4
        无操作 买入 卖出 买入 卖出    卖出初始为-nums[0]
         */
        int[][] dp = new int[n][5];
        dp[0][1] = -nums[0];
        dp[0][3] = -nums[0];

        /** 
          这个就是买卖股票Ⅱ的延伸，卖出+ 买入-
         */
        for(int i = 1 ;i < n ;i++){
            dp[i][1] = Math.max(dp[i-1][1],-nums[i]);
            dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]+nums[i]);
            dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2]-nums[i]);
            dp[i][4] = Math.max(dp[i-1][4],dp[i-1][3]+nums[i]);
        }
        return dp[n-1][4];
    }
}