The problem of the maximum difference between the left and right maxima

author ：Grey

Original address : The problem of the maximum difference between the left and right maxima

Topic link

Cattle guest ： Maximum difference between left and right maxima

describe

Given a length of N(N>1) Integer array A, Can be A Divided into left and right parts , Left part A[0..K], Right section A[K+1..N-1],K The range of values can be [0,N-2]. Find so many partition schemes , The absolute value of the maximum in the left part minus the maximum in the right part , What's the biggest ？

Given an array of integers A And array size n, Please return the answer to the question .

The test sample ：

A：[2,7,3,1,1]

n：5

return ：6

Main idea

Suppose the length of the array is len, Go through the array , Get the maximum value of the array max, Then compare 0 Location and len-1 The value of the location , Take the smaller one , Assuming that m, be max - m Is the answer .

Complete code

public class MaxGap {
    
    public int findMaxGap(int[] A, int n) {
    
        int max = A[0];
        int len = A.length;
        for (int i = 1; i < len; i++) {
    
            max = Math.max(A[i], max);
        }
        return max - (Math.min(A[0], A[len - 1]));
    }
}

prove

Because the global maximum is max, So no matter max To which part , Will become the maximum value of this part . hypothesis max It is divided into the right part , So the maximum value of the right part is max, Suppose the maximum value of the left part is m, that max - m It is a candidate for an answer . To make max - m Maximum , The left part cannot be empty , So the left part must contain 0 The value of the location , therefore , On the left only 0 Position value ,max - m To maximize , namely ：max - arr[0]; Empathy , hypothesis max Is divided to the left , The maximum value on the right is assumed to be n, To make max - n Maximum ,len - 1 The value of the position must be included on the right , that max - arr[len-1] Is the biggest . So the final answer is :

max - Math.min(arr[0],arr[len-1]);

more

Algorithm and data structure notes