solution.h

/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

typedef pair<int, int> pii;
class Solution {
   public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 1) {
            return 0;
        }

        vector<int> mi_l(n), mx_r(n);

        mi_l[0] = prices[0];
        for (int i = 1; i < n; i++) {
            mi_l[i] = min(mi_l[i - 1], prices[i]);
        }
        mx_r[n - 1] = prices[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            mx_r[i] = max(mx_r[i + 1], prices[i]);
        }
        vector<int> mx_val(n);
        mx_val[n - 1] = mx_r[n - 1] - prices[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            mx_val[i] = max(mx_val[i + 1], mx_r[i] - prices[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            int tmp = prices[i] - mi_l[i] + (i + 1 < n ? mx_val[i + 1] : 0);
            ans = max(ans, tmp);
        }
        return ans;
        }
};