Python 言語を使用して最大連続部分列合計を記述します

最大連続部分列の合計を求めることは、非常に古典的で古い面接の質問です。この記事では、Python 言語での最大連続部分列とその方法について説明します。

1. 問題の説明

配列 (Python のリスト) [1,3,-3,4,-6,-1] があると仮定し、配列内の最大の連続部分列の合計を求めます。たとえば、この配列では、最大の連続部分列の合計は 5、つまり 1+3+(-3)+4 = 5

2.O(n²) の解です

最も単純で粗雑な解way、double レイヤ ループは、maxsum を使用して、連続するサブシーケンスの最大合計を識別します。その後、各判定が更新されます。言うことはあまりありません。コードにアクセスしてください

def maxSum(list):
  maxsum = list[0]
  for i in range(len(list)):
    maxtmp = 0
    for j in range(i,len(list)):
      maxtmp += list[j]
      if maxtmp > maxsum:
        maxsum = maxtmp
  return maxsum
if __name__ == '__main__':
  list = [1,3,-3,4,-6]
  maxsum = maxSum(list)
  print "maxsum is",maxsum

実行結果

maxsum is 5

3.O(n)ソリューション

動的な場所ならどこでも解決策を見つけることができます仕様については、連続するサブシーケンスの最大合計の例について説明します。具体的には、部分列の最大連続合計は位置 0 ～ (n-1) の間のどこかで終了する必要があるため、配列が a[i] であると仮定します。次に、ループが i 番目の位置に移動するときに、前の連続したサブシーケンスの合計が 0 以下の場合、位置 i で終了する連続したサブシーケンスの最大合計が i 番目の位置の値になります。それは a[i] です。先行する連続したサブシーケンスの合計が 0 より大きい場合、位置 i で終了する連続したサブシーケンスの最大合計は b[i] = max{ b[i-1]+a[i], a[i]} になります。 b [i] は、最大の連続サブシーケンスの合計を指します。

def maxSum(list_of_nums):
  maxsum = 0
  maxtmp = 0
  for i in range(len(list_of_nums)):
    if maxtmp <= 0:
      maxtmp = list_of_nums[i]
    else:
      maxtmp += list_of_nums[i]

    if(maxtmp > maxsum):
      maxsum = maxtmp
  return maxsum
if __name__ == &#39;__main__&#39;:
  list_of_num = [1,3,-3,4,-6]
  maxsum = maxSum(list_of_num)
  print "maxsum is: ",maxsum

実行結果

maxsum is 5

上記の内容は、Python言語での最大連続部分列の説明とチュートリアルです。

関連する推奨事項:

最大連続サブシーケンスと問題

Pythonを完全マスター

シンプルなファクトリパターンのPythonバージョンの紹介

以上がPython 言語を使用して最大連続部分列合計を記述しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。