HackerRank最大子陣列

Question

所以我試圖通過HackerRank上的動態規劃跟蹤。

問題提示如下。

鑑於陣列A = {A1，A2，...，A N}的N個元素的，找到一個

毗連子陣列的非連續的（不一定是連續的）子陣列的最大可能的總和。 不應考慮空的子陣列/子序列。

輸入格式

輸入的第一行具有整數Ť。 T個案如下。每個測試用例都以整數N開頭。在下一行中，N整數代表陣列A。

約束上：

你認爲至少應該有一個元素子陣列和子序列。

輸出格式

二，分隔空間，整體表示的最大的連續和非連續的子陣列。至少應選擇一個整數並放入子陣列（在所有元素均爲負數的情況下可能需要）。

採樣輸入

2 
4 
1 2 3 4 
6 
2 -1 2 3 4 -5 

樣本輸出

10 10 
10 11 

說明
在第一種情況： 兩個連續的和非連續的元件的最大總和的所有元素的總和（因爲它們都是正數） 。

在第二種情況下： [2 -1 2 3 4] - >這形成了具有最大總和的連續子陣列。 對於不必要連續的元素組的最大和，只需添加所有的正元素。

---

我對這個解決方案是

def dp2(L): 
    max_so_far = max_ending_here = -2**31 # contig logic works 
    non_contig = [L[0]] # accounting for negative arrays 

    for i in xrange(len(L[0::])): 
     max_ending_here = max(L[i], max_ending_here + L[i])   
     max_so_far = max(max_so_far, max_ending_here) 
     # non-contiguous logic 
     if i != 0: 
      non_contig.append(max(non_contig[-1], non_contig[-1] + L[i])) 
    return map(str, (max_so_far, non_contig[-1])) 

if __name__ == '__main__': 
    test_cases = int(raw_input()) 
    for i in xrange(test_cases): 
     arr_length = int(raw_input()) 
     array = [int(i) for i in raw_input().split()] 

     print ' '.join(dp2(array)) 

所以上面的代碼通過了所有，但一個測試用例。這是非常大的，所以我決定上傳所有的測試用例到一個單元測試中，並在我的本地環境中運行，看看發生了什麼。

This

.F.. 
====================================================================== 
FAIL: test_answers_against_test_case2_outputs (__main__.TestCase2) 
---------------------------------------------------------------------- 
Traceback (most recent call last): 
    File "test_max_subarray.py", line 52, in test_answers_against_test_case2_outputs 
    self.assertEqual(result, self.outputs[idx]) 
AssertionError: Lists differ: ['2617065', '172073086'] != [u'2617065', u'172083036'] 

First differing element 1: 
172073086 
172083036 

- ['2617065', '172073086'] 
?    ^^ 

+ [u'2617065', u'172083036'] 
? +   + ^^ 


---------------------------------------------------------------------- 
Ran 4 tests in 0.951s 

FAILED (failures=1) 

有兩個數字是在問候非連續答案DP功能吐出不正確。這可能是從整數轉換爲字符串的問題嗎？

我意識到我正在比較unicode和python字符串，但它似乎並不重要，因爲我用其他方式嘗試過，所以我不認爲這是問題，但我可能是錯的。

Answer 1

我知道我出錯的地方。對於非連續邏輯，我完全放棄了我的想法，我可以簡單地將當前總和設置爲0，並且只嘗試向其中添加正整數。

如果給定數組內的所有整數都是負數，那麼只需獲取最大值並將其作爲最大和返回。

工作代碼。

def dp(L): 
    max_so_far = max_ending_here = -2**31 
    c_sum = 0 
    max_neg = -2**31 

    for i in xrange(len(L)): 
     max_ending_here = max(L[i], max_ending_here + L[i])   
     max_so_far = max(max_so_far, max_ending_here) 

     if L[i] > 0: 
      c_sum += L[i] 
     else: 
      if L[i] > max_neg: 
       max_neg = L[i] 
    if c_sum == 0: # All values were negative so just pick the largest 
     c_sum = max_neg 
    return map(str, (max_so_far, c_sum)) 

if __name__ == '__main__': 
    test_cases = int(raw_input()) 
    for i in xrange(test_cases): 
     arr_length = int(raw_input()) 
     array = [int(i) for i in raw_input().split()] 

     print ' '.join(dp(array)) 

除了使用之外python的最大功能的for循環，我選擇只保留在循環中軌的這種嘗試和不斷接近O（n）的運行時間。