ホームページ バックエンド開発 Python チュートリアル Python 言語を使用して最大連続部分列合計を記述します

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

Dec 06, 2017 am 10:42 AM
python 最大 継続的な

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

1. 問題の説明

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

2.O(n2) の解です

最も単純で粗雑な解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 サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

あるデータフレームの列全体を、Python内の異なる構造を持つ別のデータフレームに効率的にコピーする方法は? あるデータフレームの列全体を、Python内の異なる構造を持つ別のデータフレームに効率的にコピーする方法は? Apr 01, 2025 pm 11:15 PM

PythonのPandasライブラリを使用する場合、異なる構造を持つ2つのデータフレーム間で列全体をコピーする方法は一般的な問題です。 2つのデータがあるとします...

Pythonパラメーター注釈は文字列を使用できますか? Pythonパラメーター注釈は文字列を使用できますか? Apr 01, 2025 pm 08:39 PM

Pythonパラメーター注釈の代替使用Pythonプログラミングでは、パラメーターアノテーションは、開発者が機能をよりよく理解して使用するのに役立つ非常に便利な機能です...

Pythonスクリプトは、特定の場所のカーソル位置への出力をどのようにクリアしますか? Pythonスクリプトは、特定の場所のカーソル位置への出力をどのようにクリアしますか? Apr 01, 2025 pm 11:30 PM

Pythonスクリプトは、特定の場所のカーソル位置への出力をどのようにクリアしますか? Pythonスクリプトを書くときは、以前の出力をカーソル位置にクリアするのが一般的です...

なぜ私のコードはAPIによってデータを返しているのですか?この問題を解決する方法は? なぜ私のコードはAPIによってデータを返しているのですか?この問題を解決する方法は? Apr 01, 2025 pm 08:09 PM

なぜ私のコードはAPIによってデータを返しているのですか?プログラミングでは、APIが呼び出すときにヌル値を返すという問題に遭遇することがよくあります。

uvicornは、serving_forever()なしでhttpリクエストをどのように継続的に聞いていますか? uvicornは、serving_forever()なしでhttpリクエストをどのように継続的に聞いていますか? Apr 01, 2025 pm 10:51 PM

UvicornはどのようにしてHTTPリクエストを継続的に聞きますか? Uvicornは、ASGIに基づく軽量のWebサーバーです。そのコア機能の1つは、HTTPリクエストを聞いて続行することです...

文字列を介してオブジェクトを動的に作成し、Pythonでメソッドを呼び出す方法は? 文字列を介してオブジェクトを動的に作成し、Pythonでメソッドを呼び出す方法は? Apr 01, 2025 pm 11:18 PM

Pythonでは、文字列を介してオブジェクトを動的に作成し、そのメソッドを呼び出す方法は?これは一般的なプログラミング要件です。特に構成または実行する必要がある場合は...

Python hourglassグラフ図面:可変未定義エラーを避ける方法は? Python hourglassグラフ図面:可変未定義エラーを避ける方法は? Apr 01, 2025 pm 06:27 PM

Python:Hourglassグラフィック図面と入力検証この記事では、Python NoviceがHourglass Graphic Drawingプログラムで遭遇する可変定義の問題を解決します。コード...

Windowsの下のpython .whlファイルをどこからダウンロードしますか? Windowsの下のpython .whlファイルをどこからダウンロードしますか? Apr 01, 2025 pm 08:18 PM

Pythonバイナリライブラリ(.whl)のダウンロードメソッドは、Windowsシステムに特定のライブラリをインストールする際に多くのPython開発者が遭遇する困難を調査します。一般的な解決策...

See all articles