给定一个数组，我能在O(n)中找到最长的范围吗?

For a given array of integers, find the maximum distance between 2 points (i and j) that have higher values ​​than any element between them.

对于给定的整数数组，找到两个点(i和j)之间的最大距离，它们之间的值比它们之间的任何元素都高。

Example:

例子:

values: 0 10  8  9  6  7  4 10  0
index : 0  1  2  3  4  5  6  7  8 

for the values above the solution is i=1, j=7, but

对于上面的值，解是i=1, j=7，但是

• if the value of index 7 is 9 instead of 10 the solution is i=3, j=7
• 如果指数7的值是9而不是10，那么解就是i=3 j=7
• if the value of index 7 is 7 instead of 10 the solution is i=5, j=7
• 如果指数7的值是7而不是10，那么答案是i=5 j=7

I can't see a solution in O(n) ... anyone ?

我看不到O(n)的解。有人知道吗?

7 个解决方案

#1

A simple stack based solution. Iterate over the array left to right, with the stack holding elements (technically, indexes, but use values for comparisons) that are either:

一个简单的基于堆栈的解决方案。遍历从左到右的数组，其中包含的堆栈元素(技术上是索引，但使用值进行比较)可以是:

1. The largest from the left (i.e. no larger or equal element between the start of the array and the element)
2. 从左边开始的最大的元素(即数组和元素之间没有较大或相等的元素)
3. The largest since the previous element on the stack.
4. 这是自堆栈上的前一个元素以来最大的。

When processing the next element x, pop elements smaller than x as long as they are from the category 2. above, then push x on the stack. Obviously you need to keep the current max to be able to discern between category 2 and 1 in constant time.

当处理下一个元素x时，弹出小于x的元素，只要它们来自第2类。在上面，然后在堆栈上按x。显然，您需要保持当前的最大值，以便能够在恒定时间内分辨第2和第1类。

The processing above is O(n) - each element can be pushed at most once and popped at most once. Having the final stack, just check neighboring pairs (on the stack) - one of the pairs is the solution. This too is O(n).

上面的处理是O(n)——每个元素都可以最多推一次，最多弹出一次。有了最后的堆栈，只需检查邻近的对(堆栈上的)——其中一个对就是解决方案。这也是O(n)。

Here's a picture with what should stay on the stack (the fat rectangles) after the whole scan of the array:

这是一幅图片，在整个数组扫描之后应该保留在堆栈上的内容(矩形):

(There's a small mistake in the above picture: fourth bar from the left should either be thick or drawn shorter than the first one, sorry)

(上面的图片中有一个小错误:左边的第四格应该比第一个粗，或者画得短，抱歉)

Why this works: the final stack contains all elements of the input array that are not between any two larger elements (I've skipped the case of an element between two equal elements) . The solution is obviously a neighboring pair of such elements.

为什么这样做:最终堆栈包含输入数组的所有元素，它们不在任何两个较大的元素之间(我跳过了两个相等元素之间的元素的情况)。很明显，解是这类元素的邻对。

Here's an implementation in Python:

下面是Python中的一个实现:

from collections import namedtuple

E = namedtuple('E', 'i x')

def maxrange(iterable):
    stack = [E(0, None)]*2 # push sentinel values
    maxsofar = None

    top = lambda: stack[-1] # peek at the top element on the stack

    for i, x in enumerate(iterable):
        while top().x < x and top().x < maxsofar:
            stack.pop()
        stack.append(E(i, x)) # push
        maxsofar = max(maxsofar, x)

    return max(b.i-a.i for a,b in zip(stack, stack[1:]))

Example:

例子:

>>> maxrange([2,1,3])
2

#2

I believe that the following algorithm runs in O(n) time and produces an optimal solution. It's a bit tricky, so I'll split the logic into two cases, one in which we consider the case where there are no duplicate values in the array, and one in which we considered a case where duplicates are allowed.

我相信下面的算法在O(n)时间内运行并产生一个最优解。这有点棘手，所以我将把逻辑分成两种情况，一种是我们考虑数组中没有重复值的情况，另一种是我们考虑允许重复值的情况。

The key data structure we'll be using is the Cartesian tree, which is a max-heap built out of a range of data with the property that an inorder walk of the nodes of the tree produce the values of the sequence in the order in which they appear. The critical detail is that it's possible to build a Cartesian tree for a sequence of elements in O(n) time.

我们将要使用的关键数据结构是笛卡尔树，它是一个基于一系列数据构建的最大堆，其属性是树的节点以顺序遍历的方式产生序列的值。关键的细节是可以在O(n)时间内为一系列元素构建一个笛卡尔树。

As an example, given the sequence 4 1 0 3 2, we would get this Cartesian tree:

举个例子，给定序列4 1 0 3 2，我们会得到这个笛卡尔树

        4
         \
          3
         / \
        1   2
         \
          0

Notice that the inorder walk does indeed give back 4 1 0 3 2.

注意，inorder walk确实返回了4 1 0 3 2。

I now claim that the endpoints of the range we're looking for must be a parent/child pair in the Cartesian tree (that is, either the first node is a parent of the second node or vice-versa). Note that we are not looking for a node and any ancestor, but specifically a parent/child pair. To prove this, I prove the following two claims:

我现在断言，我们要查找的范围的端点必须是笛卡尔树中的父/子对(即，要么第一个节点是第二个节点的父节点，要么相反)。注意，我们不是在寻找节点和任何祖先，而是在寻找父/子对。为了证明这一点，我证明以下两点:

Claim 1: Any parent/child pair in the Cartesian tree defines a range of values in the original sequence that does not have any intermediary values greater than the endpoints.

断言1:笛卡尔树中的任何父/子对定义了原始序列中的一组值，这些值没有任何中间值大于端点。

Claim 2: Any range of values in the sequence that does not have any intermediary values greater than its endpoints must have those endpoints as a parent/child pair in the Cartesian tree.

断言2:序列中没有任何中间值大于其端点的任何值的范围都必须将这些端点作为笛卡尔树中的父/子对。

Taken together, these collectively prove that the range we're looking for must be a parent/child pair in the Cartesian tree. This then gives us an easy linear-time algorithm for solving the problem when all the values are distinct. First, in O(n) time, build up a Cartesian tree for the range. Next, recursively explore the tree, and for each parent/child pair, find the distance between those pairs, taking the largest range we find. This second step also runs in O(n), since a Cartesian tree is a binary tree and so the number of edges is O(n).

综上所述，这些集合证明了我们所寻找的范围必须是笛卡尔树上的父/子对。这就给了我们一个简单的线性时间算法来解决所有的值都是不同的问题。首先，在O(n)时间内，为范围构建一个笛卡尔树。接下来，递归地探索树，对于每个父/子对，找到这些对之间的距离，取我们找到的最大范围。第二个步骤也在O(n)中运行，因为笛卡尔树是二叉树，所以边的数目是O(n)。

Proof of claim one: A parent/child pair must look like either

声明一:父/子对必须看起来像。

 u
  \
   v
  / \
 A   B

or

或

    u
   /
  v
 / \
A   B

Recall that a Cartesian tree stores its elements in a way that an inorder traversal of the elements of the tree yield the elements of the array used to produce the tree in the order in which they appear in the array. This means that in case (1), we're looking at a range of elements starting with u, containing all of A, and concluding with b. Similarly, in case (2), the range starts with v, then contains all of B, then terminates with u. We prove the claim that u and v have no values in-between them that are larger than either u or v by contradiction. Suppose this were the case and that the value w is bigger than either u or v. By the definition of a Cartesian tree, if w is in-between u and v in the original sequence, then in case (1) it must be in subtree A and in case (2) it must be in subtree B. But a Cartesian tree is a max-heap, and so in case (1) both u and v are bigger than everything in A, and in case (2) both u and v are bigger than everything in B, a contradiction. Thus the range of values between any parent/child pair must be no larger than either the parent or the child.

回想一下，笛卡尔树以一种方式存储其元素，这种方式是树的元素遍历元素，生成树的元素，它们以数组中出现的顺序生成树。这意味着(1),我们看到一系列元素从u,包含所有的结束和b。同样,(2),范围从v,包含所有的b,然后终止和你在一起。我们索赔证明u和v没有中间值大于u或v的矛盾。假设是这样,w的值大于u或v笛卡尔树的定义,如果w是中间u和v在原始序列,然后在(1)必须在子树,例(2)必须在子树但笛卡尔树max-heap,所以在例(1)u和v都是大于一切的,如果(2)u和v都大于B的一切,一个矛盾。因此，任何父/子对之间的值范围必须不大于父或子对。

Proof of Claim 2: By contrapositive; we show that if there is a subsequence of the original array beginning with u and ending with v that contains an element larger w than either u or v, then u and v cannot be a parent/child or child/parent pair in the Cartesian tree. The proof is virtually identical to above - if u and v were a parent/child pair, then in case (1) above w would have to be in A and in case (2) w would have to be in B, in both cases violating the fact that a Cartesian tree is a max-heap.

权利要求证明2:相反地;我们证明，如果原始数组的子序列以u开头，以v结尾，包含一个大于u或v的元素，那么u和v就不能是笛卡尔树中的父/子或子/父对。上面的证据几乎是相同的——如果u和v是一对父/子,然后在上面(1)w必须在例(2)和w必须在B,在这两种情况下违反这一事实max-heap笛卡尔树。

The above proofs show us that if all the values are distinct, we can solve this problem in linear time by just building a Cartesian tree and doing a simple tree walk. But what happens if the elements are allowed to be duplicates, as in your original problem statement? In that case, we can use a modified Cartesian tree structure. We'll allow nodes to be combined into a "metanode" of multiple different Cartesian tree values that share the same value. For example, the sequence 2 7 1 7 8 0 3 8 2 would look like this:

上面的证明告诉我们，如果所有的值都是不同的，我们可以用线性时间来解决这个问题，只需要建立一个笛卡尔树，然后做一个简单的树漫步。但是，如果元素被允许重复，比如在最初的问题声明中，会发生什么?在这种情况下，我们可以使用一个修正的笛卡尔树结构。我们将允许将节点组合成具有相同值的多个不同的笛卡尔树值的“metanode”。例如，序列2 7 7 7 8 0 3 8 2看起来是这样的:

                  [8 ------- 8]
                  / \         \
                 /   3         2
                /   /
               /   0
              /
          [7 -- 7]
            / \
           2   1

Here, the root is a metanode consisting of two nodes with value 8, and the first 8 metanode consists of two 7 metanodes.

在这里，根是一个metanode，由两个节点组成，值为8，前8个metanode由两个7个metanodes组成。

For notational purposes, let the "leftest" node of a metanode be the node furthest to the left in the metanode, and let the "rightest" node of a metanode be the node furthest to the right in a metanode.

出于标注的目的，让metanode的“左”节点作为metanode中最左的节点，让metanode的“最右”节点作为metanode中最右的节点。

In this modified Cartesian tree, we can define an inorder walk of the nodes as one that visits all of the nodes in a metanode in left-to-right order, doing an inorder walk of each of the nodes it contains. We then enforce that the modified Cartesian tree a strict max-heap (every node must be strictly greater than any of its children) and that an inorder walk of the tree yields the values in the same order in which they appear in the original sequence.

在这个修改后的笛卡尔树中，我们可以将节点的无序遍历定义为以从左到右的顺序访问metanode中的所有节点，对其包含的每个节点进行顺序遍历。然后，我们强制将修改后的笛卡尔树设置为严格的max-heap(每个节点必须严格大于它的任何子节点)，并且对树进行无序的遍历会产生与它们在原始序列中出现的顺序相同的值。

Notice that this generalized construction contains our original solution as a special case - if all the values are distinct, nothing is different in this tree structure. I'll also state without proof that it's possible to build up one of these structures in O(n) by a straightforward modification of the standard Cartesian tree algorithm.

请注意，这个广义构造包含了我们作为特殊情况的原始解——如果所有的值都是不同的，那么在这个树结构中没有什么是不同的。我还没有证明可以通过简单地修改标准笛卡儿树算法在O(n)中建立一个这样的结构。

In this modified tree structure, a range of values with no intervening values at least as large as the endpoints corresponds to either:

在这个修改后的树结构中，没有插入值的取值范围至少与端点对应的值相同:

1. A parent and the rightest node of its left child.
2. 它的左子节点的父节点和右节点。
3. A parent and the leftest node of its right child.
4. 父节点及其右子节点的最左节点。
5. Two adjacent nodes in the same metanode.
6. 两个相邻的节点，在同一个metanode上。

The proof of the first two claims is pretty much a straightforward modification of the proof for the above case. The difference is that instead of the contradiction proof saying that it would violate the max-heap property, instead you would claim that it violates the strong max-heap property. You would also say that any equal values in the middle of the range would have to manifest themselves as nodes that would prevent the range endpoints from being leftest or rightest nodes in a metanode. The proof of the third claim is (roughly) that any nodes in-between the two nodes must be strictly smaller than the endpoints, and if there were an equal value in the middle then the two nodes wouldn't be adjacent metanodes.

前两种说法的证明基本上是对上述情况的证明的简单修改。不同之处在于，与其用矛盾证明它会违反max-heap属性，不如说它违背了strong max-heap属性。您还会说，范围中间的任何相等值都必须显示为节点，以防止范围端点在metanode中成为最左或最右的节点。第三个断言的证明是(粗略地)，两个节点之间的任何节点都必须严格小于端点，如果中间有相等的值，那么两个节点就不会是相邻的metanodes。

Given this observation, we can solve the original problem in O(n) time as follows. First, build up a generalized Cartesian tree from the input range. Next, walk the tree and look at all of the indicated pairs of elements that might be the range, picking the largest one that you find. Since for each node only a constant number of other nodes need to be checked (its parent, left and right siblings, and children give at most five nodes to check), this can be done in O(n) time for a net runtime of O(n).

有了这个观察，我们可以在O(n)时间内解出原来的问题。首先，从输入范围构建一个广义笛卡儿树。接下来，走到树中，查看所有可能是范围的元素对，选择您找到的最大的元素。由于每个节点只需要检查一定数量的其他节点(它的父节点、左节点和右节点以及子节点最多要检查5个节点)，这可以在O(n)时间内完成，在O(n)时间内完成。

Whew! That was an awesome problem. I don't know if this is an ideal solution, but it at least proves that it's possible to do this in O(n) time. If someone comes up with a better answer, I'd love to see it.

唷!这是个可怕的问题。我不知道这是不是一个理想的解，但它至少证明了在O(n)时间内做这个是可能的。如果有人能提出更好的答案，我很想看看。

#3

Rafals solution is good, but we can do without the stack and so save some memory. Here is a short and efficient implementation in O(n) time:

Rafals解决方案很好，但是我们可以不用堆栈，这样可以节省一些内存。以下是O(n)时间内的一个简短而有效的实现:

def highDist(seq):
    res, ltr, rtl = 0, 0, 0
    for i in range(len(seq)):
        if seq[i] >= seq[ltr]:
            res = max(res, i-ltr)
            ltr = i
        if seq[-i-1] >= seq[-rtl-1]:
            res = max(res, i-rtl)
            rtl = i
    return res

Run on the example input:

在示例输入上运行:

>>> print highDist([0, 10, 8, 9, 6, 7, 4, 10, 0])
6
>>> print highDist([0, 10, 8, 9, 6, 7, 4, 9, 0])
4
>>> print highDist([0, 10, 8, 9, 6, 7, 4, 7, 0])
2
>>> print highDist([])
0

The trick is, that if we have two points a and b s.t. everything between them is smaller than them, then the maximum distance we are searching for, is either |b-a| or entirely outside the range. Hence if we partition the entire sequence that way, one of them is the range we are searching for.

关键是，如果我们有两个点a和b，它们之间的所有东西都比它们小，那么我们要寻找的最大距离，要么是|b-a|要么完全超出范围。因此如果我们这样划分整个序列，其中一个就是我们要搜索的范围。

We can make the partition easily be creating an upsequence from each end.

我们可以让这个分区很容易地从每一端创建一个向上的序列。

#4

The linear solution is quiet simple. We will use two pointer, for endings of segment, such that every element on it is not more than the the first element. For the fixed first element (first pointer) we move second pointer right until it points to smaller or equal to the first element. If element at second pointer is great or equal to the first, we can update answer with current segment length. And if it points to an element strictly greater than first one, we have to move first pointer to current position, because no mo segment can start at it's last position - current element will be more than segment's endpoint.

线性解很简单。我们将使用两个指针，用于段的结尾，这样它上面的每个元素都不超过第一个元素。对于固定的第一个元素(第一个指针)，我们将第二个指针往右移动，直到它指向小于或等于第一个元素。如果第二个指针的元素是大的或等于第一个，我们可以用当前段长度更新答案。如果它指向的元素严格大于第一个元素，我们必须将第一个指针移到当前位置，因为没有一个mo段可以从它的最后一个位置开始——当前元素将大于段的端点。

This algorithm find maximum by length segment with left element less or equal to right element, so we need to repeat same actions one more time - walking from right to left.

该算法通过左元素小于或等于右元素的长度段找到最大值，因此我们需要再次重复同样的动作——从右到左行走。

Complexity - O(n), just moving n-1 times second pointer and no more than n-1 times first pointer.

复杂度- O(n)，移动n-1乘以第二个指针，不超过n-1乘以第一个指针。

If my idea is not clear ask any questions.

如果我的想法不清楚，请提任何问题。

#5

ETA: Found some errors, sorry. I'll get back at this after work, it is definitely an intriguing problem.

发现一些错误，抱歉。我下班后再谈这个，这绝对是一个有趣的问题。

Written in sort of pseudocode; the idea is to move a window of three numbers over the array and perform certain comparisons, then update your left and right positions accordingly.

用伪代码写的;我们的想法是在数组上移动一个由三个数字组成的窗口，并进行一定的比较，然后相应地更新左和右的位置。

// Define the initial window
w1=a[0], w2=a[1], w3=a[2]
// Will hold the length of the current maximum interval
delta_max = 0

// Holds the value of the current interval's leftmost value
left=max(w1,w2,w3)
// Holds the position of the current interval's leftmost value
lpos= *position of the chosen wi above*

// Holds the position of the current interval's rightmost value
rpos = lpos + 1
// Holds the value of the current interval's rightmost value
right = a[rpos]

i = 0
// Holds the position of the max interval's leftmost value
lmax = 0
// Holds the position of the max interval's rightmost value
rmax = 0

while (i<n-3) do
    i = i + 3
    w1=a[i], w2=a[i+1], w3=a[i+2]

    if (w1<left) and (w2<left) and (w3<left)
        right = w3
        rpos = i + 2
    else
        // Set the new left to the first value in the window that is bigger than the current left
        if (w1>left): left = w1, lpos = i
        else
            if (w2>left): left = w2, lpos = i+1
            else
                if (w3>left): left = w3, lpos = i+2


    delta = rpos-lpos
    if delta>dmax: dmax = delta, lmax = lpos, rmax = rpos
    lpos = rpos
    rpos = lpos + 1
    right = a[rpos]
end

#6

I am not sure whether the following solution is O(n), but it is certainly 'almost O(n)', and also very simple, just a few lines of code. It is based on the following observation. For any pair of indices (i,j), draw an arc between them if the interval [i,j] has the sought-after property. Now observe that it is possible to draw these arcs so that they do not intersect. Then observe that the smallest pairs are (i,i+1) - all of these have the sought property. Next, a bigger pair can always be constructed by contraction of two smaller pairs. This leads to the following structure: Start with the pairs (i,i+1) in a linked list. Go over the linked list repeatedly, and try to contract consecutive links. This algorithm is order-indepedent because of the non-intersection property. Perl code follows.

我不确定下面的解决方案是否为O(n)，但它肯定是“差不多O(n)”，而且非常简单，只有几行代码。它是基于以下观察。对于任意一对指标(i,j)，如果区间[i,j]具有炙手可热的性质，则在它们之间画一条弧。现在注意，画出这些弧是可能的，这样它们就不会相交。然后观察最小的对是(i,i+1)——所有这些都具有所寻找的属性。其次，更大的一对可以通过收缩两个小的对来构造。这就导致了以下结构:从一个链表中的对(i,i+1)开始。反复检查链接列表，并尝试收缩连续的链接。该算法由于非交叉性的性质，是一种不确定的算法。Perl代码。

#!/usr/local/bin/perl -w
use strict;

my @values    = (0, 10, 8, 9, 6, 7, 4, 10, 0);           # original example.
@values       = map { int(100 * rand()) } 1..100;        # random testing.
my $nvalues   = @values;
my @intervals = (1..$nvalues-1);       # this encodes a linked list 0->1, 1->2, N-2->N-1

my $change = 0;
my ($maxi, $maxj) = (0, 1);            # initial solution
my $maxdelta = 1;

do {
   my ($jstart, $j) = (0, $intervals[0]);
   $change = 0;
   while ($j < $nvalues-1) {
      my $jnext = $intervals[$j];
      while ($jnext < $nvalues -1 && $values[$j] == $values[$jnext]) {
          $jnext = $intervals[$jnext];   # lookahead to skip intervals with identical boundaries
      }
      if ($values[$j] < $values[$jstart] && $values[$j] < $values[$jnext]) {
         $intervals[$jstart] = $jnext;                   # contraction step
         print STDERR "contraction to $j $jnext\n";
         $change = 1;
         $j = $jnext;
         if ($jnext - $jstart > $maxdelta) {
            $maxdelta = $jnext - $jstart;
            ($maxi, $maxj) = ($jstart, $jnext);
         }
      }
      else {
         ($jstart, $j) = ($j, $intervals[$j]);
      }
   }
   print STDERR "---\n";
}
while ($change);


my $jstart = 0;

while ($jstart < $nvalues -1) {
   my $jnext = $intervals[$jstart];
   local $, = " ";
   print STDERR @values[$jstart..$jnext], "\n";
   $jstart = $jnext;
}

print STDERR "solution $maxi $maxj\n";

#7

I have write a solution for the problem. So far looks valid, works with all input I have tried. This is the code in C++. I wanted a solution as clean and simple I could get so didn't use Cartesian tree or stack solution suggested but rather a simpler approach: parsing first time and get the list of valid intervals (as suggested by Rafał Dowgird) and a second time to determine the max len interval that is the solution.

我已经为这个问题写了一个解决方案。到目前为止看起来是有效的，适用于我尝试过的所有输入。这是c++中的代码。我想要一个解决方案是干净和简单的我可以不使用笛卡尔树或堆栈的解决方案建议,而是一个更简单的方法:解析第一次和得到的有效间隔(建议RafałDowgird)和第二次的马克斯len区间来确定解决方案。

void Solution(const int* vData, int vLen) { typedef std::pair Interval; typedef std::vector ListaIntervaleType; ListaIntervaleType ListaIntervale;
空解决方案(const int* vData, int vLen) {typedef std::对间隔;typedef std::向量ListaIntervaleType;ListaIntervaleType ListaIntervale;

/************************************************************************/
/* Get valid Intervals                                                  */
/************************************************************************/
#define IS_LAST_ELEM (i == vLen-1)

int iIdxStart = -1;
for (int i=1; i < vLen; ++i)
{
    if (-1 == iIdxStart)
    {
        /* Searching for Interval START */

        if (!IS_LAST_ELEM)
        {
            if (vData[i+1] < vData[i])
            {
                iIdxStart = i;
            }
        }


    }
    else
    {
        /* Searching for Interval END */

        if (vData[iIdxStart] <= vData[i] || IS_LAST_ELEM)
        {
            /* stop condition: crt val > start value*/
            ListaIntervale.push_back(std::make_pair(iIdxStart,i));

            if (!IS_LAST_ELEM && vData[i+1] < vData[i])
            {
                iIdxStart = i;
            }
            else
            {
                iIdxStart = -1;
            }
        }



    }

}

/************************************************************************/
/* Concatenate intervals                                                */
/************************************************************************/

//int iMaxLenIntervalIdx = -1;
//int iMaxLenIntervalVal = 0;

ListaIntervaleType::iterator crt;
//for (crt=ListaIntervale.begin(); crt!=ListaIntervale.end(); crt++)
//{
//  ListaIntervaleType::iterator next = crt + 1;
//  if (next != ListaIntervale.end())
//  {
//      if (crt->second == next->first)
//      {
//          if (crt->second < crt->first && 
//              crt->second < next->second)
//          {
//              //concatenam
//              crt->second =  next->second;
//              crt = ListaIntervale.erase(next);
//          }
//      }
//  }
//}


/************************************************************************/
/* Get Max                                                              */
/************************************************************************/

ListaIntervaleType::iterator solution = ListaIntervale.begin();
int iMaxLen = 0;

for (crt=ListaIntervale.begin(); crt!=ListaIntervale.end(); crt++)
{
    int iCrtLen = crt->second - crt->first;
    if (iCrtLen > iMaxLen)
    {
        iMaxLen = iCrtLen;
        solution = crt;
    }

}   

/************************************************************************/
/* Print Solution                                                       */
/************************************************************************/

if (solution != ListaIntervale.end())
{
    wprintf(L"Solution idx=[%d-%d] val=[%d-%d]", solution->first, solution->second, vData[solution->first], vData[solution->second]);
}
else
{
    wprintf(L"Solution NOT FOUND");
}


return;

}

}