求数组中两个元素差的最大值（后面的元素减去前面的元素）O(N)时间复杂度O(1)空间复杂度 题目：在数组中找到两个元素，计算后面的元素减去前面的元素的差。求出所有差的最大值。 （你可以认为你在炒股票，买入价格和卖出价格就是你的盈利）

//数组A[0...n] , 对于0<=i
    
     <=n, 找出A[j]-A[i]的最大值 public class MaxDifference {
      public static void main(String[] arg) {
          int[] a = {12, 20, 23, 1, 2, 5, 7, 10};         //动态规划         System.out.println(maxDifference(a)); //后面减前面, 最大差值         //动态规划         int[] b = {13, 20, 23, 1, 2, 5, 7, 10};         System.out.println("动态规划" + maxDifference1(b));         //暴力搜索         System.out.println("暴力搜索: " + maxDifference2(a));         System.out.println("暴力搜索: " + maxDifference2(b));         //转化法         System.out.println("转化法: " + maxDifference4(a));     }     //自底向上动态规划: O(n)     //后面的数减去前面的数     public static int maxDifference(int[] a){
          int minLeft = a[0];//默认最小的值         int maxDiff = a[1] - a[0]; //初始最大差值         for(int i = 2; i < a.length; i++)         {
              if(a[i - 1] < minLeft)//得到i之前数组的最小值             {
                  minLeft = a[i - 1];             }             if(a[i] - minLeft > maxDiff)//获取最大差值             {
                  maxDiff = a[i] - minLeft; //用当前值减去当前值之前的最小值, 得到最大差值             }         }         return maxDiff;     }     //前面的数减去后面的数     public static int maxDifference1(int[] a){
          int maxLeft = a[0];//默认最大的值         int maxDiff = a[0] - a[1]; //初始最大差值         for(int i = 2; i < a.length; i++)         {
              if(maxLeft < a[i - 1])//得到i之前数组的最大值             {
                  maxLeft = a[i - 1];             }             if(maxLeft - a[i] > maxDiff)//获取最大差值             {
                  maxDiff = maxLeft - a[i]; //用当前值之前的最大值减去当前值, 得到最大差值             }         }         return maxDiff;     }     //分治法: 最大值和最小值都在左边数组中, 最大值最小值都在右边数组中, 最大值最小值分别位于左边数组或者右边数组中     //O(nlgn)     public static int maxDifference3(int[] a){
          return 0;     }     //转换法     /*     1、有一数组array[n]，数组长度为n     2、构建一个长度为n-1的辅助数组array2[n-1]，且array2[i] = array[i] - array[i+1]; （0<=i
     
      i），即array[i] + array2[i+1] + ... + array2[j]，     有(array[i] - array[i+1]) + (array[i+1] -array[i+2]) + ... + (array[j] - array[j+1]) = array[i] - array[j+1]     分析至此，发现数组中最大的数对之差（即array[i] - array[j+1]）其实是辅助数组array2中最大的连续子数组之和。      */     public static int maxDifference4(int[] a){
          //int[] b = Arrays.copyOf(a, a.length); //对a进行深拷贝, 长度可以自定义         int[] temp = new int[a.length - 1];         for (int i = 0; i < temp.length; i ++){
              temp[i] = a[i+1] - a[i];         }         int sum = 0;         for (int i = 0; i < temp.length; i ++){
              if (sum <= 0){
                  sum = temp[i];             }else {
                  sum += temp[i];             }         }         return sum;     }     //暴力搜索 O(n^2)     public static int maxDifference2(int[] a){
          int max = 0;         for (int i = 0; i < a.length - 1; i ++){
              for (int j = i + 1; j < a.length; j ++){
                  if (a[j] - a[i] > max){
                      max = a[j] - a[i];                 }             }         }         return max;     }     //寻找下标差值最大的两个数     //动态规划 }