动态规划

原理：https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/
时间复杂度：O(n)
空间复杂度：O(n)

import java.util.*;

public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        // write code here
        Long sum = 0L;    //！！！注意返回值是长整型
        int[] maxLeft = new int[arr.length];
        int[] maxRight = new int[arr.length];

        for (int i = 1; i < arr.length; i++) maxLeft[i] = Math.max(maxLeft[i - 1], arr[i - 1]);
        for (int i = arr.length - 2; i >= 0; i--) maxRight[i] = Math.max(maxRight[i + 1], arr[i + 1]);

        for (int i = 1; i < arr.length - 1; i++) {
            int min = Math.min(maxLeft[i], maxRight[i]);
            if (min > arr[i]) sum += min - arr[i];
        }

        return sum;
    }
}