0

我必须编写一个函数，它接受一个整数列表并返回列表的最大总和子列表。一个例子是：

l = [4,-2,-8,5,-2,7,7,2,-6,5]

返回19

到目前为止，我的代码是：

count = 0
for i in range(0,len(l)-1):
    for j in range(i,len(l)-1):
        if l[i] >= l[j]:

            count += l[i:j]

return count

我有点卡住和困惑，有人可以帮忙吗？谢谢你！

4

3 回答 3

0

这称为“最大子阵列问题”，可以在线性时间内完成。维基百科文章有你的答案。

于 2013-03-13T07:51:16.410 回答
0

我认为这是一个家庭作业，所以我不会在这里尝试谷歌算法和/或发布太多代码。

一些想法（只是从我的脑海中，因为我喜欢这些类型的任务:-)）

正如用户 lc 已经指出的那样，天真且详尽的方法是测试每个子列表。我相信您的 (user2101463) 代码朝着这个方向发展。只需用于sum()建立总和并与已知的最佳值进行比较。要使用合理的起始值初始化最知名的总和，只需使用列表的第一个值。

the_list = [4,-2,-8,5,-2,7,7,2,-6,5]

best_value = the_list[0]
best_idx = (0,0)
for start_element in range(0, len(the_list)+1):
    for stop_element in range(start_element+1, len(the_list)+1):
        sum_sublist = sum(the_list[start_element:stop_element])
        if sum_sublist > best_value:
            best_value = sum_sublist
            best_idx = (start_element, stop_element)

print("sum(list([{}:{}])) yields the biggest sum of {}".format(best_idx[0], best_idx[1], best_value))

这当然具有二次运行时间 O(N^2)。这意味着：如果由输入列表的元素数量定义的问题大小随着 N 的增长而增长，则运行时间随着 N*N 的增长而增长，并且具有一些任意系数。

一些改进的启发式方法：

  • 显然负数不好，因为它们减少了可实现的总和
  • 如果遇到负数序列，如果到目前为止的最佳列表加上负数的总和 < 0，请在该序列之后重新启动最佳子列表。在您的示例列表中，前三个数字不能成为最佳列表的一部分，因为的积极影响4总是被 否定-2, -8。
  • 可能这甚至会导致O(N)实现从头到尾迭代，记住最知名的开始索引，同时计算从该开始索引的完整总数的运行总和以及最后一个连续的正数和负数序列的正负小计， 分别。
  • 一旦找到这样的最佳列表，可能需要进行最终清理以删除尾随的负面子列表，-6, 5例如示例末尾的 。

希望这会导致正确的方向。

于 2013-02-25T14:13:55.213 回答
0

最佳解决方案是采用 O(n) 的线性运行时间。但是这个问题有“n*lgn”运行时解决方案（基于分治算法）和“n^2”运行时解决方案。如果你对这些感兴趣这里的算法是强烈推荐的算法的链接介绍，在这里我用java编写了一个具有线性运行时的代码。

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int []A=new int[n];
    int highestsum=Integer.MIN_VALUE;
    int sumvariable=0;
    int x=0;
    for(int i=0;i<n;i++)
    {
        A[i]=sc.nextInt();
    }
    for(int i=0;i<n;i++)
    {
        sumvariable+=A[i];
        if(sumvariable<0)
        {
            if(sumvariable>=highestsum)
            {
                highestsum=A[i];
                sumvariable=A[i];
            }
            else
            {
                sumvariable=0;
            }
        }
        else
        {
            if(sumvariable>highestsum)
            {
                highestsum=sumvariable;
            }

        }
    }
    System.out.println(highestsum);
}
于 2016-07-04T12:29:15.067 回答