寻找最大的连续间隔，这样从开始到结束之间的所有数都大于开始，小于结束。

Question

你已经给出了整数数组

例如5，3，4，3，9，4，4，6，6，5，7

你必须找出最大区间(i，j)，使i和j之间的所有数在i处大于等于数，而在J处小于数。数字不必按顺序排列。我的数字也应该小于j的数。

在上面的例子中，有两个这样的间隔: 3,4,3,9和4,4,6,8

在3,4,3,9 -中间两个数字(4,3)大于等于起始数(3)，但小于等于结束数(9)。启动数(3)也小于结束数(9)。

在4,4,6,8 -中间两个数字(4,6)大于等于起始数(4)，但小于等于结束数(8)。启动数(4)也小于结束数(8)。

解决这个问题的一种方法是检查大小n的所有区间，然后再检查n-1，直到得到这样的区间为止。但我想要的是高效的分而治之，或征服/DP/或其他方法。

Answer 1

我们可以在O(n log n)中通过将每个元素看作区间中最左边的潜在元素来解决这个问题。对于每个这样的候选元素，(1)在右侧找到低于它的第一个元素--这是可能间隔的右边的一个界，因为包含这样的元素将使约束失效；(2)在区间中找到最大值元素的最左边的实例(或者最右边的元素，如果允许A[j]等于它左边的一个元素)--这是间隔可以扩展的最右边而不使约束无效。

我们可以使用堆栈存储O(n)中所有元素的(1)答案。我们可以预处理一个范围最大查询的结构，该结构将在O(log n)时间内回答(2)的第一部分。一旦找到了间隔的最大值，如果数组中有其实例的有序列表(我们可以用哈希表在O(n)中进行预处理)，我们就可以在O(log n)时间间隔中找到最右边或最左边的实例。

Answer 2

DP给出了一个简单的答案，希望它能帮到你：

public class Test {

    public static void main(String[] args){

        int[] input = {5,3,4,3,9,4,4,6,8,6,5,7};

        //
        // lenDp array to store the max possible interval sizes starting at every index.
        //
        int[] lenDp = new int[input.length];
        //
        // minNumIdxs array to store the indexes of minimum numbers in all sub arrays with the same length
        //
        int[] minNumIdxs = new int[input.length];

        //
        // for a start, every number is an interval with size of 1,
        // and there are as many sub arrays with length of 1 as input.length,
        // the minimum number in a sub array is the first number:
        //
        for(int i = 0; i < input.length; i++){
            lenDp[i] = 1;
            minNumIdxs[i] = i;
        }

        int maxLen = 1;

        //
        // check all possible intervals of size from 2 to input.length
        //
        for(int len = 2; len <= input.length; len++){
            //
            // for every possible interval with size of `len`, the starting index can be in range of [0, input.length - len]
            //
            for(int i = 0, end = input.length - len; i <= end ; i++ ){

                //
                // assume the interval of size `len` is possible for index i,then the number at input[i] has to be the minimum number,
                // and the number at input[i + len - 1] has to be greater than or equal to
                // the largest number ( at input[i + dp[i] - 1] ) of the current interval starting at index i.
                // in the corner case where dp[i] == 1 and len > 2, it wouldn't be valid, for example:
                // when len = 5, i = 0, dp[i] = dp[0] = 1, then input[i + len - 1] = input[0 + 5 - 1] = input[4] = 9;
                // 9 is greater than 5 (input[0]), but it's invalid.
                // So we also need to check (len == 2 || dp[i] > 1)
                //
                if(minNumIdxs[i] == i && input[i + len - 1] >= input[i + lenDp[i] - 1] &&
                        (len == 2 || lenDp[i] > 1)){
                    lenDp[i] = len;
                    maxLen = len;
                }

                //
                // update the index of the minimum number in the sub array starting at i
                //
                if(input[i + len - 1] < input[minNumIdxs[i]])minNumIdxs[i] = i + len - 1;
            }
        }



        //
        // print out the final result
        //
        for(int i = 0 ; i < lenDp.length ; i++){
            if(lenDp[i] == maxLen){
                System.out.println(Arrays.toString(Arrays.copyOfRange(input, i, i + maxLen)));
            }
        }

    }

}

产出：

 [3, 4, 3, 9]
 [4, 4, 6, 8]