范围内最高最矮树高度差问题

Question

问题：N棵树排成一排。考虑到每棵树的高度H，小明被要求回答M个问题。每个问题包含两个数字L和R，询问间隔[L，R]中最高树和最短树之间的高度差。帮助小明解决这个问题

输入的第一行包含两个整数N和M，表示树的数量和问题的数量
以下N行中的每一行都包含一个整数Hi，表示每棵树的高度。以下M行中的每一行都包含两个整数Li和Ri，表示每个问题的间隔。
输出：从第1行到第m行，每行包含一个整数，表示从第Lth树到第Rth树的最高树和最短树之间的高度差。

Answer 1

tree[i]代表第i棵树的高度
假设dp[i][j][0] 代表[i，j]区间最大值，dp[i][j][1]代表[i，j]区间最小值
可知dp[i][j][0] = dp[i][j][1] = tree[i] 当i=j时
dp[i][j][0]= Max(tree[j]，dp[i][j-1][0]) j>i
dp[i][j][1]= Min(tree[j]，dp[i][j-1][1]) j>i
最后求解[x，y]区间，为dp[x][y][0] - dp[x][y][1]