/*
 * Two-pass greedy / 兩趟貪婪：
 *   Pass 1 (L→R): ensure each child > left neighbor when its rating is higher.
 *   Pass 2 (R→L): ensure each child > right neighbor when its rating is higher.
 *   Answer = sum of max(left[i], right[i]).  O(n) time, O(n) space.
 */

#include <stdlib.h>   // malloc, free / 動態配置與釋放

int candy(int* ratings, int ratingsSize) {
    int n = ratingsSize;                       // 別名 n，方便閱讀 / alias for readability
    if (n <= 1) return n;                      // 0 或 1 個小孩直接回傳 / trivial cases: 0 or 1 child

    // 配置兩個輔助陣列，分別記錄左、右方向的需求
    // Allocate two helper arrays for the left-side and right-side requirements
    int* left  = (int*)malloc(sizeof(int) * n);   // 每個 int 4 bytes，共 n 個 / n ints on the heap
    int* right = (int*)malloc(sizeof(int) * n);   // 同上 / same

    // 第一趟：從左到右 / Pass 1: left to right
    for (int i = 0; i < n; i++) {
        // 如果不是第一個，且評分比左鄰居高，糖果就比左鄰居多 1
        // If not first and rating beats left neighbor, take left[i-1] + 1
        if (i > 0 && ratings[i] > ratings[i - 1]) {
            left[i] = left[i - 1] + 1;          // 嚴格遞增 / strict +1 over previous
        } else {
            left[i] = 1;                        // 否則重設為最低值 1 / otherwise reset to floor 1
        }
    }

    // 第二趟：從右到左 / Pass 2: right to left
    for (int i = n - 1; i >= 0; i--) {
        // 如果不是最後一個，且評分比右鄰居高，糖果就比右鄰居多 1
        // If not last and rating beats right neighbor, take right[i+1] + 1
        if (i < n - 1 && ratings[i] > ratings[i + 1]) {
            right[i] = right[i + 1] + 1;        // 從右邊累積 / accumulate from the right
        } else {
            right[i] = 1;                       // 否則重設為 1 / otherwise reset to 1
        }
    }

    // 加總每個位置兩方向需求的最大值，就能同時滿足兩個條件
    // Sum the max of the two directions at each index
    int total = 0;                              // 累加器 / running total
    for (int i = 0; i < n; i++) {
        int a = left[i];                        // 左方向需求 / left-side need
        int b = right[i];                       // 右方向需求 / right-side need
        total += (a > b) ? a : b;               // 三元運算子取較大者 / ternary picks the larger
    }

    free(left);                                 // 釋放配置的記憶體，避免洩漏 / free heap memory
    free(right);                                // 同上 / same
    return total;                               // 回傳最少糖果總數 / return the minimum total
}