найти любую подпоследовательность увеличения с размером 3 в неупорядоченном массиве

Question

Я столкнулся с вопросом в Интернете: найдите любую подпоследовательность увеличения с размером 3 в неупорядоченном массиве, используя сложность времени O (n). (просто нужно вернуть один действительный результат)

For example: 
1 2 0 3 ==> 1 2 3 
2 4 7 8 ==> 2 4 7; 4 7 8; 2 4 8 (anyone of them is Okay) 

Это довольно относительно длинной подпоследовательности увеличения. Но это также очень специфично: мы просто хотим размер 3. Я выбрал O (N) решение, которое требует сканирования массива дважды.

The idea: 
(1) For each element, find is there any one smaller than it on the left side, is there any one larger than it on the right side. 
(2) We can compute a minimum pre-array and a maximum post-array as pre-processing. For example: 
1 2 0 3 ==> minimum pre-array: none 1 1 0 
1 2 0 3 ==> maximum post-array: 3 3 3 None 

Мне интересно, есть ли другие решения для этого?

Answer 1

Вы пытались найти cs.stackexchange?

Это уже решена здесь: https://cs.stackexchange.com/questions/1071/is-there-an-algorithm-which-finds-sorted-subsequences-of-size-three-in-on-ti

Одна идея состоит в том, чтобы сделать что-то вроде длинного увеличивающейся алгоритма подпоследовательности, и делает это в один проход.

В этом вопросе я связываю несколько решений.

Answer 2

Вот решение вопроса относится к (в JavaScript)

Комментарии http://www.geeksforgeeks.org/find-a-sorted-subsequence-of-size-3-in-linear-time/ другие альтернативные решения.

function findIncSeq3(arr) { 
var hi = Array(arr.length); 
var lo = Array(arr.length); 
hi[arr.length - 1] = lo[0] = null; 
var tmp, i; 
for (i = arr.length - 2, tmp = arr.length - 1; i >= 0; i--) { 
    if (arr[i] >= arr[tmp]) { 
    tmp = i; 
    hi[i] = null; 
    } else { 
    hi[i] = tmp; 
    } 
} 
for (i = 1, tmp = 0; i < arr.length; i++) { 
    if (arr[i] <= arr[tmp]) { 
    tmp = i; 
    lo[i] = null; 
    } else { 
    lo[i] = tmp; 
    } 
} 
for(i = 0; i < arr.length; i++) { 
    if(hi[i] !== null && lo[i] != null) { 
    return [arr[lo[i]], arr[i], arr[hi[i]]]; 
    } 
} 
return null; 
} 

console.log("1,2,5", findIncSeq3([1, 2, 0, 5])); 
console.log("null", findIncSeq3([5, 4, 3, 2, 1])); 
console.log("2,3,9", findIncSeq3([10, 8, 6, 4, 2, 5, 3, 9])); 

EDIT Вот одна версия итерации.

function findIncSeq3(arr) { 
var tmp = Array(arr.length); 
for(var i = 0, s = arr.length - 1, lo = 0, hi = arr.length -1; i <= s; i++) { 
    if(s - i !== hi) { 
     if(arr[s - i] >= arr[hi]) { 
      hi = s - i; 
     } else if(tmp[s - i] !== undefined) { 
      return [arr[tmp[s - i]], arr[s - i], arr[hi]]; 
     } else { 
      tmp[s - i] = hi; 
     } 
    } 
    if(i !== lo) { 
     if(arr[i] <= arr[lo]) { 
      lo = i; 
     } else if(tmp[i] !== undefined) { 
      return [arr[lo], arr[i], arr[tmp[i]]]; 
     } else { 
      tmp[i] = lo; 
     } 
    } 
} 
return null; 
}