最大的一筆連續的子陣列（面試問題）

可能重複：
Find the maximum interval sum in a list of real numbers.最大的一筆連續的子陣列（面試問題）

我提出以下問題在今天接受採訪的Adobe軟件工程師的位置。

問題給定整數的數組arr[1..n]。編寫一個算法來查找數組中具有最大總和的連續子數組的總和。如果所有數字都是負數，則返回0。

例

鑑於陣列arr[1..6] = [ 12, 14, 0, -4, 61, -39 ]

回答

83構成。

我可以拿出一個運行在O(n logn)的解決方案，但我不認爲它是非常有效的。面試官要求我寫一個O(n)算法。我無法想出它。

有關如何爲此問題編寫O(n)解決方案的任何想法？算法要在C/C++/Java中實現。

在此先感謝

來源

2011-03-21 WebDev

有沒有在「編程珠璣」在這個問題上一整章 - 推薦閱讀。 – 2011-03-21 13:42:39

這是一個非常簡單的問題。一個接一個地從兩端穿過。並且從每一端開始修整數組，直到從開始到當前位置或從結束到當前位置的總和爲負。 O（n） – 2011-11-25 10:19:02

您可以使用Kadane's algorithm它運行在O（N）。

這裏是算法（從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

來源

2011-03-21 13:34:52

這是維基百科文章的鏈接以供參考：http://en.wikipedia.org/wiki/Maximum_subarray_problem – 2011-03-21 13:37:32

這個數組如何處理：[-12,14,0，-4,61，-39]實際結果：[-12，14，0，-4，61]預計：[14，0，-4，61] – 2011-04-13 01:30:12

最大的一筆連續的子陣列（面試問題）

回答

相關問題