1

我正在尝试查找具有以下 2 个属性的列表的子列表（至少有一个正整数） 1. 它的元素之和为正 2. 它具有所有其他子列表的最大长度和正和

我只对那个列表的长度感兴趣。Kadane 的算法在 O(n) 时间内找到总和最大的子列表。有没有一种算法可以在 O(n) 中做同样的事情？我找到了一个解决方案，但它确实计算了所有子列表，当然非常慢......

感谢您的时间

4

4 回答 4

0

一个可能的解决方案在这里。您可以使用计数排序对数组进行排序。在该凝视形式之后，最大元素进行求和并检查是否添加此元素将保留非的正和，如果它仍然为正，则添加并递增计数继续前进。这可能对某些输入有一些错误，我的意思是它可能不适用于所有测试用例。但是，这只是一个可能对您有所帮助的想法，因为对此进行一些改进将为您提供所需的输出。在一个遍历计数变量结束时会给你结果。例子：

array=[12,10,8,5,4,-2,-3,-20,-30] //considered already sorted now
i=0 sum=12 count=1
i=1 sum=22 count=2
i=2 sum=30 count=3
i=3 sum=35 count=4
i=4 sum=39 count=5
i=5 sum=37 count=6
i=6 sum=34 count=7
i=7 sum=14 count=8
i=8 sum=14 count=8 //as now 30 cant be added
so, here count=8 says maximum length sub array of 8 can give you positive sum.
于 2013-11-03T09:52:27.910 回答
0

由于在您的回答中您将子列表视为后续元素，我想对 Kadane 的算法稍作修改将适合您。只需引入一个名为max_length_till_now的变量。并在您发现长度大于当前值的子列表时更新它。

于 2014-12-14T06:50:51.710 回答
0

好的，你几乎已经回答过了。只需修改 Kadane 以使用子序列的长度而不是子序列的总和。这解决了你的问题。这是来自维基百科的 Kadane：

int sequence(int numbers[])    
{ 
    // These variables can be added in to track the position of the subarray
    size_t begin = 0;
    size_t begin_temp = 0;
    size_t len_temp = 0;
    size_t end = 0;

    // Find sequence by looping through
    for(size_t i = 1; i < numbers.size(); i++)
    {
            // calculate max_ending_here
            if(max_ending_here < 0)
            {
                    max_ending_here = numbers[i]; 
                    begin_temp = i;
            }
            else
            {
                    max_ending_here += numbers[i];
                    len_temp += (i - begin_temp);
            }

            // calculate max_so_far_len
            if(len_temp >= max_so_far_len )
            {
                    max_so_far_len  = len_temp; 
                    begin = begin_temp;
                    end = i;
            }
    }
    return max_so_far_len ;

}

于 2014-01-23T13:55:37.160 回答
0

计算所有数字的总和说它是n。如果 n > 0 则返回完整列表作为答案。否则继续从两端修剪较小的元素并从总和中减去，直到总和变为正数。返回 this 作为结果。这是一个 O(n) 算法。希望能帮助到你

于 2012-12-13T11:51:48.547 回答