3

maxSubArray の合計と、関連する開始インデックスと終了インデックスを取得するメソッドを実装しようとしています。参考までに、maxSubArray は、整数の合計がすべての subArray の中で最大になる連続した subArray です。合計は正しく、終了インデックスも正しいのですが、先頭を取得するのに問題があります。些細なケースを 1 つ説明しましたが、何をしても、すべてのケースを説明することはできないようです。私が1つを説明すると、別のものが現れます。線形時間で合計を取得することは明らかに可能ですが、正しい開始インデックスを効率的に取得する方法がわかりません。 

def maxSubArray(seq):
    #max_i = max ending at i, max_gen = best max up until i
    max_i = max_gen = beg = end = prev_max = 0

    for i in xrange(len(seq)):
        #use dynamic programming to get maxSubArray sum (works)
        max_i = max(0, max_i + seq[i])
        max_gen = max(max_gen, max_i)

        #get correct end (works)
        if prev_max < max_gen:
            end = i

        prev_max = max_gen

    if max_gen == 0:
        max_gen = max(seq)
        beg = end = seq.index(max_gen)

    return [max_gen, beg, end]

私が言ったように、私は多くのことを試しましたが、すべての新しい方法が新しい/古い問題を引き起こすため、それらを削除し続けます. 誰にもアドバイス/解決策はありますか？Java タグで同様の質問を見ましたが、回答が正しくありませんでした。便宜上、動作することを知っている力ずくの方法と、私が使用してきたミニテスターを含めました。

def bruteForceCheck(seq):
    maxV = [float('-inf'), 0, 0]

    for i in xrange(len(seq)):
        for j in xrange(i,len(seq)):
            if (sum(seq[i:j+1]) > maxV[0]):
                maxV = [sum(seq[i:j+1]), i, j]

    return maxV

if __name__ == "__main__":

    for i in xrange(1000):
        l = []
        for j in xrange(15):
            num = random.randint(-1000,1000)

            #didn't feel like dealing with issue of two methods 
            #choosing to count or not count 0s
            while (num == 0):
                num = random.randint(-1000,1000)

            l.append(num)

        msa = maxSubArray(l)
        bfc = bruteForceCheck(l)

        if msa != bfc:
            print l
            print msa
            print bfc
            break
4

2 に答える 2

2

申し訳ありませんが、これは動作し、Pythonic です。

def maxSubArray(seq):
    all_sum = cur_sum = 0
    all_beg = cur_beg = 0
    all_end = 0
    for cur_end, x in enumerate(seq, 1):
        if cur_sum + x > 0:
            cur_sum += x
            if all_sum < cur_sum:
                all_sum = cur_sum
                all_beg, all_end = cur_beg, cur_end
        else:
            cur_sum = 0
            cur_beg = cur_end
    return all_sum, all_beg, all_end

アルゴリズムは同じです。ここで終わる配列 ( cur_) と全体 ( all_) の合計、開始インデックス、および終了インデックスがあります。

編集:ここでの終了インデックスは排他的であることに注意してください。

また、複数の最適な部分配列がある場合、これは最初で最も長いものを返します。

于 2013-10-30T04:25:36.357 に答える