左右最值最大差

给定一个长度为N(N>1)的整型数组A，可以将A划分成左右两个部分，左部分A[0..K]，右部分A[K+1..N-1]，K可以取值的范围是[O,N-2]。求这么多划分方案中，左部分中的最大值减去右部分最大值的绝对值，最大是多少?

import java.util.*;

public class MaxGap {
    public int findMaxGap(int[] A, int n) {
        // write code here
        int max = A[0];
        for(int i=1; i<A.length; i++){
            if(max < A[i]){
                max = A[i];
            }
        }
        int min = A[0]>A[n-1]?A[n-1]:A[0];
        return max - min;
    }
}

import java.util.*;

public class MaxGap {
    public int findMaxGap(int[] A, int n) {
        int max = A[0],min;
        for (int i = 0; i < n; i++){
            if (A[i] > max){
                max = A[i];
            }
        }
        min = A[0] < A[n-1] ? A[0] : A[n-1];
        return max-min;
    }
}

import java.util.*;

public class MaxGap {
    public int findMaxGap(int[] A, int n) {
         int k =n-2;
        int MAX = 0;
        for (int i = 0; i <= k ; i++) {
            int[] num1 = new int[i+1];
            int[] num2 = new int[n-(i+1)];
            for (int j = 0; j < num1.length ; j++) {
                num1[j] = A[j];
            }
            Arrays.sort(num1);
            int maxLeft = num1[num1.length-1];
            int p =i+1;
            for (int m = 0; m < num2.length ; m++) {
                num2[m] = A[p];
                p++;
            }
            Arrays.sort(num2);
            int maxRight = num2[num2.length-1];
            if(MAX < Math.abs(maxLeft-maxRight)){
                MAX = Math.abs(maxLeft-maxRight);
            }
        }
        return MAX;
    }
}

import java.util.*;

public class MaxGap {
    public int findMaxGap(int[] A, int n) {
        int max0 = A[0];
        int[] b = new int[n];
        b[n - 1] = A[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            b[i] = A[i] > b[i + 1] ? A[i] : b[i + 1];
        }
        int maxGap = 0;
        for (int k = 0; k < n - 1; k++) {
            if(A[k]>max0) max0=A[k];
            int gap = Math.abs(max0 - b[k + 1]);
            if(gap>maxGap) maxGap=gap;
        }
        return maxGap;
    }
}

import java.util.*;

public class MaxGap {
    public int findMaxGap(int[] A, int n) {
        // write code here
        int mmax = -1;
		for(int k = 0 ; k < n -1 ; k ++){
			int maxLeft = -1;
			int maxRight = -1;
			for(int i = 0 ; i < n ; i ++){
				if(i <= k){
					maxLeft = Math.max(maxLeft,A[i]);
				}else {
					maxRight = Math.max(maxRight,A[i]);
				}
			}
			mmax = Math.max(Math.abs(maxLeft-maxRight),mmax);
		}
		return mmax;
    }
}

import java.util.*;

public class MaxGap {
    public int findMaxGap(int[] A, int n) {
        // write code here
        //从左边只有A[0]开始
        int lmax = A[0];
        int rmax = Integer.MIN_VALUE;
        int gap = 0;
        for(int i=0;i<A.length-1;i++){//循环次数
            //left-->A[0]~A[i],right-->A[i+1]~A[n-1]            
            lmax = Math.max(lmax,A[i]);            
            for(int j=i+1;j<A.length;j++){
                rmax = A[j];
                rmax = Math.max(rmax,A[j]);
            }            
            gap = Math.max(gap,Math.abs(lmax-rmax));
        }
        return gap;
    }
}
为何不能完全通过？

方法二：
import java.util.*;

public class MaxGap {
    public int findMaxGap(int[] A, int n) {
        
        /*
        本题用循环来做结果没有完全作对，后来想了一下，本题无非就是两种情况：
        （1）左侧所有数组中最大值的最大值  -  右侧所有数组中的最大值的最小值（左越长越好，又越短越好）
        （2）左侧所有数组中最大值的最小值  -  右侧所有数组中的最大值的最大值（左越短越好，又越长越好）
        最后取（1）（2）中的最大的、
        对于（1）：left--> A[0]~A[n-2], right-->A[n-1]
        对于（2）：left--> A[0],        righ-->A[1]~A[n-1]
        */
        int max = A[0];
        for(int i=0;i<A.length;i++){
            if(max<A[i]){max=A[i];}
        }
        return max-Math.min(A[0],A[n-1]);        
    }
}

最原始的办法，分别找到左边与右边的最大值，相减取绝对值。
不过本题的说法不严谨。。。有点歧义 
public int findMaxGap(int[] A, int n)
	{
        int maxDisOfTwoGroup = Integer.MIN_VALUE;
        for(int k = 0; k <(n-1);k++)
        {
        	int maxNumberOfLeft = A[0];
            for(int i = 0; i <= k ; i++)
            {
            	if(A[i] > maxNumberOfLeft)
            		maxNumberOfLeft = A[i];
            }
            
            int maxNumberOfRight = A[k+1];
            for(int i = (k+1); i < n ;i++)
            {
            	if(A[i] > maxNumberOfRight)
            		maxNumberOfRight = A[i];
            }
            
            if((maxNumberOfLeft-maxNumberOfRight) 
            		> maxDisOfTwoGroup)
            {
            	maxDisOfTwoGroup = 
            			Math.abs(maxNumberOfLeft-maxNumberOfRight);
            }
        }
        
        System.out.println(maxDisOfTwoGroup);
        return maxDisOfTwoGroup;
    }

import java.util.*;
public class MaxGap {
    public int findMaxGap(int[] A, int n) {
		int max = 0;
		for (int i = 0; i < n - 1; i ++ ) {
			int max1 = max(A, 0, i);
			int max2 = max(A, i + 1, n - 1);
			int temp = Math.abs(max1 - max2);
			max = max > temp ? max : temp;
		}
		return max;
	}
	public static int max(int[] A, int start, int end) {
		int res = 0;
		for (int i = start; i <= end; i ++ ) 
			res= res > A[i] ? res : A[i];
		return res;
	}
}

import java.util.*;

public class MaxGap {
    public int findMaxGap(int[] A, int n) {
        // write code here
        int max = 0;
        for(int i = 0;i<n;i++){
            if(A[i] > max){
                max = A[i];
            }
        }
        int min = Math.min(A[0],A[n-1]);
        return Math.abs(max - min);
    }
}

//简单说一下，不用开辟额外的空间，直接在本数组操作即可
//用三个指针就可以。一个指向K，其余两个以K为分界线，分别指向开头和K+1的位置
public int findMaxGap(int[] A, int n) {
        //leftmax存放左边数组的最大值，rightmax存放右边数组的最大值
        //value存放差值，temp存放每次的最大值
        int leftmax = 0 , rightmax = 0 ,value = 0 , temp = 0;
        //以K为分界线，K每次不断移动指针
        for(int K = 0 ; K < n-1 ; K++){
            //做一个判断。如果是第一次从左到K找最大数
            //就进入for循环，如果不是第一次找最大数，
            //因为前面已经在K-1个数中找到了最大数，所以不用从新开始找
            //只需要和第K个数比较一下就可以了
            if (value != 0 && A[K] > leftmax) {
                leftmax = A[K];
            } else {
                leftmax = A[0];
                // i每次从0开始遍历到K的位置，并且返回最大值
                for (int i = 0; i <= K; i++) {
                    leftmax = A[i] > leftmax ? A[i] : leftmax;
                }
            }
            rightmax = A[K+1];
            //j从K+1处开始遍历，并且返回数组最大值
            for(int j = K+1 ;j<n ; j++){
                rightmax = A[j]>rightmax?A[j]:rightmax;
            }
            //记录差值
            value = leftmax - rightmax;
            //差值小于0，取绝对值
            value = value<0?-value:value;
            //如果当前差值比上次差值大，替换差值
            temp = value>temp?value:temp;
        }
        //返回差值
        return temp;
    }