数据结构与算法面试题:给定 n 个非负整数 a1,a2,a3,…,an,每个数代表坐标中的一个点(i, ai),请找出两个点之间的最大距离。...(提示:动态规划)
简介:给定 n 个非负整数 a1,a2,a3,…,an,每个数代表坐标中的一个点(i, ai),请找出两个点之间的最大距离。...(提示:动态规划)
算法思路
算法实现思路:
使用动态规划的方法进行求解。具体来说,用left[i]表示第i个数左侧最小的数,用right[i]表示第i个数右侧最大的数。...) {
int n = nums.size();
vector left(n, 0), right(n, 0); // 定义两个数组分别存储对于每个元素i来说的左边最小和右边最大的数...关键在于对left和right数组更新方法的理解,这样才能理解所编写代码的含义。