给定一个无序整数数组和若干区间查询，每个查询给出区间的左右端点，要求返回每个区间内的最大值。请设计并实现算法，并分析时间复杂度。

回答思路

1. 能清晰描述问题并明确输入输出
2. 能给出暴力解法并分析其复杂度
3. 能提出更优方案（如线段树、稀疏表、莫队等）并说明适用场景
4. 能正确实现所选算法并处理边界情况
5. 能准确分析时间复杂度和空间复杂度