每日一道算法题(10)—最大数对差

题目 ：在一个数组中，每一个元素与其右侧元素的差值构成一个数对之差。请找出所有数对之差中的最大值。例如，在数组{2, 4, 1, 16, 7, 5, 11, 9}中，最大的数对之差为11，其来源于16减去5的结果。

1.核心思路阐述

Solution1: 通过将其转化为计算最大子数组问题的问题来实现。引入一个辅助数组diff，其长度为n-1。按照公式diff[i] = diff[i] - diff[i+1]进行计算。随后找出具有最大值的子数组，并确定对应的起始位置low与结束位置high。此时，所求的最大差值即为data[low]减去data[high+1]的结果。

Solution2: 采用动态规划的方法进行处理。假设在data[i]中减去某一数值后，当前最大的数对差为currentMax。那么对于data[i-1]而言，其最大数对差应取data[i-1]-data[i]与data[i-1]-data[i]+currentMax两者中的较大值。通过从数组末尾向前依次遍历，同时记录下currentMax及其对应的low和high位置，最终即可输出结果。

该算法的时间复杂度为O(n)，空间复杂度则为O(1)。

2.代码

solution2：

 #include"iostream"

    
 using namespac