// Algorithm: Components are contiguous ranges. A cut between i and i+1 occurs
// when prefMax[i] <= sufMin[i+1] (every left value <= every right value, so no
// forward/backward jump can cross). Precompute sufMin, then sweep with running
// prefMax M; close each group at every cut and fill ans[left..i] with M.
// 演算法：分量必為連續區間；當前綴最大值 ≤ 後綴最小值即為切點。

#include <stdlib.h>  // malloc/free 動態記憶體 / dynamic memory

int* maxValue(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;                                  // LeetCode 透過指標回傳長度 / LeetCode reads length back via pointer
    int* ans = (int*)malloc(sizeof(int) * numsSize);         // 配置答案陣列 / allocate answer array on heap
    int* sufMin = (int*)malloc(sizeof(int) * numsSize);      // 後綴最小值陣列 / suffix-min scratch array

    sufMin[numsSize - 1] = nums[numsSize - 1];               // 最後一格的後綴最小就是它自己 / last cell's suffix min is itself
    for (int i = numsSize - 2; i >= 0; --i) {                // 從右往左填 sufMin / fill sufMin right-to-left
        // 三元運算子 ? : 等價於 if-else，取較小者 / ternary operator picks the smaller of two
        sufMin[i] = nums[i] < sufMin[i + 1] ? nums[i] : sufMin[i + 1];
    }

    int M = 0;                                               // 當前分量目前見過的最大值（前綴最大）/ running prefix max within current group
    int left = 0;                                            // 當前分量的起點索引 / start index of current group
    for (int i = 0; i < numsSize; ++i) {                     // 由左向右掃一次 / single left-to-right sweep
        if (nums[i] > M) M = nums[i];                        // 更新前綴最大值 / update prefix max with current element
        // 切點條件：到達結尾，或 M <= 右側最小（無法跨越）/ cut: end of array, or M <= sufMin[i+1] (uncrossable)
        if (i == numsSize - 1 || M <= sufMin[i + 1]) {
            for (int k = left; k <= i; ++k) {                // 把整段 [left, i] 答案填成 M / fill whole component slice with M
                ans[k] = M;                                  // 該索引可達的最大值即此分量的最大 / max reachable from k is M
            }
            left = i + 1;                                    // 下一個分量從 i+1 開始 / next group starts after the cut
            M = 0;                                           // 重置最大值（nums[i] >= 1 安全）/ reset M (safe since nums[i] >= 1)
        }
    }

    free(sufMin);                                            // 釋放暫存陣列，避免記憶體洩漏 / free scratch buffer to avoid leak
    return ans;                                              // 由 LeetCode harness 負責 free(ans) / harness frees ans
}