给定一个整数数组，求数组中每个数与其右侧所有数之差的最大值，即求 max(a[i] - a[j])，其中 i

Question

给定一个整数数组，求数组中每个数与其右侧所有数之差的最大值，即求 max(a[i] - a[j])，其中 i < j。请实现该算法并分析时间复杂度。

Accepted Answer

考察点：考察数组遍历与维护极值的算法设计能力。回答思路：正确理解问题：求所有 i<j 对中 a[i]-a[j] 的最大值 能说明暴力 O(n^2) 思路及局限 能给出一次遍历维护右侧最小值或左侧最大值的优化 能分析时间复杂度和空间复杂度 能处理空数组或单元素数组等边界情况

给定一个整数数组，求数组中每个数与其右侧所有数之差的最大值，即求 max(a[i] - a[j])，其中 i < j。请实现该算法并分析时间复杂度。