0

给定一个正整数数组，我想找出数组中非递减子序列的数量。

例如，如果数组是{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 个这样的序列

4

2 回答 2

2

这是一种算法，它将列出数字序列中的每个上升子序列：

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，comp 7>6=true，存储 [7]，[6,7]
步骤 3：开始 = 6， current=8, comp 8>7=true, store [8], [7,8], [6,7,8]
step 4: start=6, current=4, comp 4>8=false, 设置开始当前项目，存储 [4]
步骤 5：开始 = 4，电流 = 5，补偿 5>4=true，存储 [5]，[4,5]
步骤 6：开始 = 4，电流 = 6，补偿 6>5 =true，存储 [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一个二维数组并将每个序列存储seq在sequences[seq.length].

于 2015-10-02T20:48:27.547 回答
0

您可以对最长递增子序列使用类似于众所周知的二次解法的动态规划方法。

让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]

另请参阅所有最长递增子序列的数量。它只查找最长的序列，但我想它也可以修改为计算所有这些序列。

于 2015-10-02T14:41:07.457 回答