数据结构算法题/数组中两个数相减（前面减后面）的最大值

数组中两个数相减（前面减后面）的最大值。

解法一：O(n^2)

就是一个很普通的方法。求出 数组中所有下标小的元素减去下标大的元素，找出其中的最大值即可。代码如下：

//O(N^2) 找出数组arr中两个数相减的最大值
    public static int maxValueSub(int[] arr){
        int max = 0;
        int sub;
        for(int i = 0; i < arr.length; i++){
            for(int j = i+1; j < arr.length; j++){
                sub = arr[i] - arr[j];
                if(sub > max)
                    max = sub;
            }
        }
        return max;
    }

解法二：O(n)

使用两个指针，初始值设为指向第一个数和第二个数，如下图所示：

这时候再拿p1减去p2后面的值就没有意义了，因为p1<p2，拿p1减p2后面的值肯定不会比p2减去它后面的值大。因此我们把指针p1指向p2的位置，p2后移一位。如下图所示，直到p2到达数组末尾。

这里面跳过了第二幅图中p1和p2中间的数相减的情况，当p1指向9，p2指向18,9和18之间的两个数相减有没有可能更大呢？可以证明不存在这种情况。假设p1和p2之间存在两个数n1和n2有n1-n2更大，由于p2是第一个大于p1的数，所以n1<p1,，那么p1-n2>n1-n2,矛盾，可知这种情况不存在。时间复杂度O(n).

/**
 * 数组中两个数相减（前面减后面）的最大值
 * 两个指针p1和p2
 * 时间复杂度O(n)
 */
public class ArrMaxMinus2 {
    int GetMaxOfFormerSubLatter(int[] arr)
    {
        int p1 = 0;
        int p2 = 1;
        int max = arr[p1] - arr[p2];
        int n = arr.length-1;
        while(p2 < n)
        {
            while(arr[p2] < arr[p1] && p2 < n)
            {
                if(arr[p1] - arr[p2] > max)
                    max = arr[p1] - arr[p2];
                ++p2;
            }
            //arr[p2] > arr[p1] 后面遇到更大的元素，那么就把p1置位p2,新的p2后移一位
            p1 = p2;
            ++p2;
        }

        return max;
    }

    public static void main(String[] args) {
        ArrMaxMinus2 arrMaxMinus = new ArrMaxMinus2();
        int[] arr = {9,1,7,18,3,-5,20,4,0,5};
        System.out.println(arrMaxMinus.GetMaxOfFormerSubLatter(arr));
    }
}