我有一个数组的数组.我需要找到2个数字之间的最大差异,但最大数字在数组中的最小数字之前.
public static int maximalDrop (int [] a)
例如:
对于数组5,21,3,27,12,24,7,6,4,结果将是23(27 - 4)
对于阵列5,21,3,22,12,7,26,14,结果将是18(21-3)
我的解决方案是取数组中的第一个元素(这个数字将是大的)并检查数字和数组中所有其他数字之间的差异,之后做同样的事情,但是数组中的下一个数字和当然比较差异并返回最大的一个.我的解决方案是O(n²)我可以少做那件事吗？
除非我误解了这个问题,否则我相信你可以在阵列的一次传递中做到这一点.您只需要跟踪到目前为止您所看到的最大值和最大差异.当你通过数组计算当前数字和迄今为止看到的最大值之间的差异.
所以对于你的第二个例子5,21,3,22,12,7,26,14
1: 5 is first value so set maximum to 5
2: 21 > 5 so reset maximum
3: 21 - 3 = 18
4: 22 > 21 so reset maximum
5: 22 - 12 = 10
6: 22 - 7 = 15
7: 26 > 22 so reset maximum
8: 26 - 14 = 12
当较大的数字出现在较大的数字之后,当你找到一个新的最大值时,任何比它更小的数字都需要从这个新的最大值中减去.
所需答案是在此过程中看到的最大值 - 在这种情况下是在步骤3中计算的18.