题解 | #园林修剪#

以最矮的树作为观察点有两种选择

1: 将该树前面所有的树修得和它一样高，然后递归处理后面的树

2：将该树后面所有的树修得和它一样高，然后递归处理前面的树

3: 比较两种选择，选择大的，然后作相应的修理，并且返回大的

数据比较大，可能会超出和可能会超出int类型范围，因此使用long，此外不要使用循环输出数组

import java.util.HashMap;
import java.util.Scanner;

public class Main {


    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] data = new int[N];
        for (int i = 0; i < N; i++) {
            data[i] = scanner.nextInt();
        }

        max(0,data.length-1,data);

        StringBuilder stringBuilder = new StringBuilder();

        for (int i = 0; i < N; i++) {
            stringBuilder.append(data[i] + " ");
        }
        System.out.println(stringBuilder.toString());
    }


    public static long max(int l, int r, int[] data) {

        if (l > r) {
            return 0;
        }

        if (r - l == 1) {
            return data[l] + data[r];
        }

        if (r == l) {
            return data[l];
        }

        int minHeight = data[l];
        int min = l;

        for (int i = l; i <= r; i++) {
            if (data[i] < minHeight) {
                min = i;
                minHeight = data[i];
            }
        }
        
        // 有两种选择 1是将左边的进行处理， 2是将右边的进行处理
        long option1 = minHeight * 1L * (min - l + 1) + max(min + 1, r, data);;
        long option2 = max(l, min - 1, data) + minHeight * 1L * (r - min + 1);

        if (option1 > option2) {
            for (int j = l; j < min; j++) {
                data[j] = minHeight;
            }
        } else {
            for (int j = min + 1; j <= r; j++) {
                data[j] = minHeight;
            }
        }

        long max = Math.max(option1, option2);
        return max;

    }
}