0

所以我试图通过HackerRank上的动态编程轨道。

问题提示如下。

给定一个包含 N 个元素的数组 A={a1,a2,…,aN}，找出 a 的最大可能和

连续子阵列 非连续（不一定连续）子阵列。不应考虑空子数组/子序列。

输入格式

输入的第一行有一个整数T。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))

所以上面的代码通过了除了一个测试用例之外的所有测试用例。这是非常大的，所以我决定将所有测试用例上传到一个单元测试中并在我的本地环境中运行以查看发生了什么。

这

.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 字符串进行比较，但这似乎并不重要，因为我已经尝试过相反的方法，所以我认为这不是问题，但我可能是错的。

4

1 回答 1

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))

我没有在 for 循环之外使用 python 的 max 函数，而是选择在循环中跟踪此类函数，以尝试将运行时保持在 O(n) 附近。

于 2015-09-25T22:52:00.113 回答