最大的一笔连续的子阵列（面试问题） [英] Largest sum contiguous subarray (Interview Question)

问题描述

可能重复：
  <一href="http://stackoverflow.com/questions/5331040/find-the-maximum-interval-sum-in-a-list-of-real-numbers">Find最大时间间隔总和在实数的一个列表

我提出以下问题，在今天接受采访的Adobe软件工程师的位置。

I was asked the following question today at Adobe interview for the position of software engineer.

问题给定一个数组改编[1..1] 整数。写一个算法来找到具有最大总和的阵列内相邻的子阵列的总和。返回0，如果所有的数字都是负面的。

Problem Given a array arr[1..n] of integers. Write an algorithm to find the sum of contiguous subarray within the array which has the largest sum. Return 0 if all the numbers are negative.

示例

由于阵改编[1..6] = [12，14，0，-4，61，-39]

答案

83 [12，14，0，-4，61] 。

我可以在解决方案运行拿出为O（n LOGN），但我不认为这是非常有效的。问我的面试官写了 O（N）算法。我不能来了吧。

I could come up with a solution running in O(n logn) but I don't think it was very efficient. The interviewer asked to me to write an O(n) algorithm. I couldn't come up with it.

有关如何编写一个 O（N）针对此问题的解决方案，任何想法？ 算法采用C语言实现/ C ++ / Java的。

Any idea about how to write an O(n) solution for this problem? Algorithm to be implemented either in C/C++/Java.

在此先感谢

推荐答案

您可以使用 Kadane的这些运行在O算法 （N）。

下面是该算法（从这里 无耻地复制）

Here is the algorithm (shamelessly copied from here)

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far

这篇关于最大的一笔连续的子阵列（面试问题）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！