Как я могу найти количество неубывающих подпоследовательностей в массиве?

Question

Учитывая массив натуральных чисел, я хочу узнать количество неубывающих подпоследовательностей в массиве.

Например, если массив {6,7,8,4,5,6}неубывающие подпоследовательности будут {6},{7},{8},{4},{5},{6},{6,7},{7,8},{4,5},{5,6},{6,7,8},{4,5,6} так что это 12 такая последовательность

Answer 1

Это алгоритм, который будет перечислять каждую возрастающую подпоследовательность в последовательности чисел:

Set a pointer to the first item, to remember where the rising sequence starts.
Iterate over every item in the array, and for each item:  
    If the current item is not greater than the previous item:  
        Set the pointer to the current item.
    For every n = 1, 2, 3... :
        Save the last n items as a sequence until you reach the pointer.

Прогон этого алгоритма с вашим примером ввода [6,7,8,4,5,6] было бы:

Шаг 1: начало = 6, текущее = 6, магазин [6]
шаг 2: старт = 6, ток = 7, комп 7>6= истина, магазин [7], [6,7]
Шаг 3: начало = 6, текущий = 8, комп 8>7= истина, магазин [8], [7,8], [6,7,8]
шаг 4: старт = 6, ток = 4, комп 4>8= ложь, установить начало для текущего элемента, сохранить [4]
шаг 5: старт = 4, ток = 5, комп 5>4= истина, сохранение [5], [4,5]
Шаг 6: начало = 4, ток = 6, комп 6>5= истина, магазин [6], [5,6], [4,5,6]

результат: [6], [7], [6,7], [8], [7,8], [6,7,8], [4], [5], [4,5], [6 ], [5,6], [4,5,6]

Например, в javascript: (примечание: функция slice() используется для создания печатных копий массивов)

function rising(array) {
    var sequences = [], start = 0;
    for (var current = 0; current < array.length; current++) {
        var seq = [], from = current;
        if (array[current] < array[current - 1]) start = current;
        while (from >= start) {
            seq.unshift(array[from--]);
            sequences.push(seq.slice());
        }
    }
    return sequences;
}

var a = rising([6,7,8,4,5,6]);
document.write(JSON.stringify(a));

Если вы хотите получить результаты в том порядке, в котором вы написали их в вопросе: [6],[7],[8],[4],[5],[6],[6,7],[7,8],[4,5],[5,6],[4,5,6],[6,7,8] затем сделать sequences 2D массив и хранить каждую последовательность seq в sequences[seq.length],

Answer 2

Вы можете использовать подход динамического программирования, аналогичный известному квадратичному решению для самой длинной увеличивающейся подпоследовательности.

Позволять a[i] быть вашим входным массивом. Позволять c[i] быть числом неубывающих подпоследовательностей, которые заканчиваются на a[i], Вы можете легко рассчитать c[i] глядя на то, что может быть числом, предшествующим a[i] в такой подпоследовательности. Это может быть любое число a[j] что идет раньше a[i] (то есть, j<i) и это не больше (a[j]<=a[i]). Не забывайте одноэлементную подпоследовательность {a[i]} также. Это приводит к следующему псевдокоду:

c[0] = 1
for i = 1..n-1
    c[i] = 1 // the one-element subsequence
    for j = 0..i-1 
        if a[j]<=a[i]
            c[i] += c[j]

---

Смотрите также Число всех самых длинных увеличивающихся подпоследовательностей. Он ищет только самые длинные последовательности, но я думаю, что он также может быть изменен для подсчета всех таких последовательностей.