Repository: TheAlgorithms/C-Plus-Plus
File: dynamic_programming/trapped_rainwater.cpp (C++)

Code before:
 * This implementation calculates the amount of rainwater that can be trapped
 * between walls represented by an array of heights.
 * @author [SOZEL](https://github.com/TruongNhanNguyen)
 */

#include <algorithm>  /// For std::min and std::max
#include <cassert>    /// For assert
#include <cstddef>    /// For std::size_t
#include <vector>     /// For std::vector

/*
 * @namespace
 * @brief Dynamic Programming Algorithms
 */
namespace dynamic_programming {
/**
 * @brief Function to calculate the trapped rainwater
 * @param heights Array representing the heights of walls
 * @return The amount of trapped rainwater
 */
unsigned int trappedRainwater(const std::vector<unsigned int>& heights) {
    std::size_t n = heights.size();
    if (n <= 2)
        return 0;  // No water can be trapped with less than 3 walls

    std::vector<unsigned int> leftMax(n), rightMax(n);

    // Calculate the maximum height of wall to the left of each wall
    leftMax[0] = heights[0];
    for (std::size_t i = 1; i < n; ++i) {
        leftMax[i] = std::max(leftMax[i - 1], heights[i]);
    }

    // Calculate the maximum height of wall to the right of each wall
    rightMax[n - 1] = heights[n - 1];
    for (std::size_t i = n - 2; i < n; --i) {
        rightMax[i] = std::max(rightMax[i + 1], heights[i]);
    }

    // Calculate the trapped rainwater between walls
    unsigned int trappedWater = 0;
    for (std::size_t i = 0; i < n; ++i) {
        trappedWater +=
            std::max(0u, std::min(leftMax[i], rightMax[i]) - heights[i]);
    }

    return trappedWater;
}

}  // namespace dynamic_programming


Review comment (suggestion):
```suggestion
    std::vector<uint32_t> leftMax(n), rightMax(n);
```

Code after:
 * This implementation calculates the amount of rainwater that can be trapped
 * between walls represented by an array of heights.
 * @author [SOZEL](https://github.com/TruongNhanNguyen)
 */

#include <algorithm>  /// For std::min and std::max
#include <cassert>    /// For assert
#include <cstddef>    /// For std::size_t
#include <cstdint>    /// For integral typedefs
#include <vector>     /// For std::vector

/*
 * @namespace
 * @brief Dynamic Programming Algorithms
 */
namespace dynamic_programming {
/**
 * @brief Function to calculate the trapped rainwater
 * @param heights Array representing the heights of walls
 * @return The amount of trapped rainwater
 */
uint32_t trappedRainwater(const std::vector<uint32_t>& heights) {
    std::size_t n = heights.size();
    if (n <= 2)
        return 0;  // No water can be trapped with less than 3 walls

    std::vector<uint32_t> leftMax(n), rightMax(n);

    // Calculate the maximum height of wall to the left of each wall
    leftMax[0] = heights[0];
    for (std::size_t i = 1; i < n; ++i) {
        leftMax[i] = std::max(leftMax[i - 1], heights[i]);
    }

    // Calculate the maximum height of wall to the right of each wall
    rightMax[n - 1] = heights[n - 1];
    for (std::size_t i = n - 2; i < n; --i) {
        rightMax[i] = std::max(rightMax[i + 1], heights[i]);
    }

    // Calculate the trapped rainwater between walls
    uint32_t trappedWater = 0;
    for (std::size_t i = 0; i < n; ++i) {
        trappedWater +=
            std::max(0u, std::min(leftMax[i], rightMax[i]) - heights[i]);
    }

    return trappedWater;
}

}  // namespace dynamic_programming