arrays - 如何找到数组中非递减子序列的数量？

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] 运行此算法将是:

step 1: start=6, current=6, store [6]
step 2: start=6, current=7, comp 7>6=true, store [7], [6,7]
step 3: start=6, current=8, comp 8>7=true, store [8], [7,8], [6,7,8]
step 4: start=6, current=4, comp 4>8=false, set start to current item, store [4]
step 5: start=4, current=5, comp 5>4=true, store [5], [4,5]
step 6: start=4, current=6, comp 6>5=true, store [6], [5,6], [4,5,6]

result: [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] 中。