Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 3660. Jump Game IX

---

題目：


解答：

class Solution {
public:
    vector<int> maxValue(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre(n);
        vector<int> ans(n);

        pre[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            pre[i] = max(pre[i - 1], nums[i]);
        }

        int suf = INT_MAX;

        for (int i = n - 1; i >= 0; --i) {
            if (pre[i] > suf) {
                ans[i] = ans[i + 1];
            }
            else {
                ans[i] = pre[i];
            }

            suf = min(suf, nums[i]);
        }

        return ans;
    }
};