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

import java.util.*;

public class Main {
    public static void main(String[] args) {

        // 以下代码用于获取输入数据
        Scanner scan = new Scanner(System.in);
        String nStr = scan.nextLine(); // 输入一个正整数 n
        int n = Integer.valueOf(nStr); // 将 String 类型转换为 int 类型
        String pricesStr = scan.nextLine(); // 输入 n 个正整数
        String[] pricesStrList = pricesStr.split(" ");
        int[] prices = new int[n]; // 定义一个整型数组，用于存储 prices 中的所有元素
        for (int i = 0; i < n; i++) {
            prices[i] = Integer.valueOf(pricesStrList[i]);
        }

        int[] dp1 = new int[n];
        int[] dp2 = new int[n];

        int profit = 0;
        int minPrice = prices[0];
        for (int i = 1; i < n; i++) {
            if (prices[i] - minPrice > profit) {
                profit = prices[i] - minPrice;
            }
            dp1[i] = profit;
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            }
        }

        profit = 0;
        int maxPrices = prices[n - 1];
        for (int j = n - 2; j > -1; j--) {
            if (maxPrices - prices[j] > profit) {
                profit = maxPrices - prices[j];
            }
            dp2[j] = profit;
            if (prices[j] > maxPrices) {
                maxPrices = prices[j];
            }
        }

        int finalProfit = 0;
        for (int k = 0; k < dp1.length; k++) {
            finalProfit = Math.max(finalProfit, dp1[k] + dp2[k]);
        }
        System.out.println(finalProfit);
    }
}