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__ == '__main__': list_of_num = [1,3,-3,4,-6] maxsum = maxSum(list_of_num) print "maxsum is: ",maxsum
実行結果
maxsum is 5
上記の内容は、Python言語での最大連続部分列の説明とチュートリアルです。
関連する推奨事項:
以上がPython 言語を使用して最大連続部分列合計を記述しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ホットAIツール

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

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

Undress AI Tool
脱衣画像を無料で

Clothoff.io
AI衣類リムーバー

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

人気の記事

ホットツール

メモ帳++7.3.1
使いやすく無料のコードエディター

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

ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境

ドリームウィーバー CS6
ビジュアル Web 開発ツール

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

ホットトピック











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

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

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

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

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

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

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

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