HackerRank 最大子数组

Question

所以我正在尝试通过 HackerRank 上的动态规划轨道。

问题提示如下

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

的最大可能和

连续子数组Non-contiguous（不一定连续）子数组。空subarrays/subsequences不考虑。

输入格式

输入的第一行有一个整数T。 T 个案例。每个测试用例都以一个整数 N 开头。在下一行中，N 个整数表示数组 A.

的元素

约束条件：
$1 <= T <= 10$
$1 <= N <= 10^5$
$-10^4 <= a_i <= 10^4$

你考虑的子数组和子序列应该至少有一个元素。

输出格式

两个，space分隔，整数表示最大连续和non-contiguous子数组。至少应选择一个整数并将其放入子数组（在所有元素均为负数的情况下可能需要这样做）。

示例输入

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

示例输出

10 10
10 11

说明
在第一种情况下：连续元素和 non-contiguous 元素的最大总和是所有元素的总和（因为它们都是正数）。

第二种情况： [2 -1 2 3 4] --> 这形成了具有最大总和的连续 sub-array。对于not-necessarily-contiguous组元素的最大和，只需将所有正元素相加即可。

我对此的解决方案是

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

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

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 函数吐出的 non-contiguous 答案，有两个数字不正确。这可能是从整数转换为字符串的问题吗？

我意识到我正在将 unicode 与 python 字符串进行比较，但这似乎并不重要，因为我已经尝试过相反的方式，所以我认为这不是问题所在，但我可能是错的.

Answer 1

我知道我错在哪里了。对于非连续逻辑，我完全忘记了我可以简单地将当前总和设置为 0，并且只尝试向其添加正整数。

如果给定数组中的所有整数都是负数，则只需获取最大值 return 作为最大总和。

工作代码。

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

HackerRank 最大子数组

HackerRank The Maximum SubArray

python

algorithm

kadanes-algorithm