だから私はHackerRankの動的プログラミング トラックを通過しようとしています。
問題のプロンプトは次のとおりです。
N 要素の配列 A={a1,a2,…,aN} が与えられた場合、a の可能な最大合計を見つけます。
連続した部分配列 非連続 (必ずしも連続しているとは限らない) 部分配列。空のサブアレイ/サブシーケンスは考慮しないでください。
入力フォーマット
入力の最初の行には整数Tがあります。Tケースが続きます。各テスト ケースは、整数Nで始まります。次の行では、配列Aの要素を表すN 個の整数が続きます。
制約:
考慮するサブ配列とサブシーケンスには、少なくとも 1 つの要素が必要です。
出力フォーマット
2 つの、スペースで区切られた、最大連続部分配列および非連続部分配列を示す整数。少なくとも 1 つの整数を選択してサブ配列に入れる必要があります (これは、すべての要素が負の場合に必要になる場合があります)。
サンプル入力
2
4
1 2 3 4
6
2 -1 2 3 4 -5
サンプル出力
10 10
10 11
説明
最初のケース: 隣接する要素と隣接しない要素の両方の最大合計は、すべての要素の合計です (それらはすべて正であるため)。
2 番目のケース: [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))
したがって、上記のコードは 1 つのテスト ケースを除くすべてに合格します。これは非常に大きいので、すべてのテストケースを単体テストにアップロードし、ローカル環境で実行して何が起こっているかを確認することにしました。
.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 関数が吐き出す連続していない回答に関して、2 桁が正しくありません。これは int から文字列への変換の問題でしょうか?
ユニコードと python 文字列を比較していることに気づきましたが、逆に試してみたので問題ないようですので、それが問題だとは思いませんが、間違っている可能性があります。