検索

最大子序列和问题

Jun 07, 2016 pm 04:13 PM
順序整数最大入力質問

问题描述: 输入一组整数,求出这组数字子序列和中最大值。也就是只要求出最大子序列的和,不必求出最大的那个序列。例如: 序列:-2 11 -4 13 -5 -2,则最大子序列和为20。 序列:-6 2 4 -7 5 3 2 -1 6 -9 10 -2,则最大子序列和为16。 下面依次给出几个不

问题描述:

输入一组整数,求出这组数字子序列和中最大值。也就是只要求出最大子序列的和,不必求出最大的那个序列。例如:

序列:-2 11 -4 13 -5 -2,则最大子序列和为20。

序列:-6 2 4 -7 5 3 2 -1 6 -9 10 -2,则最大子序列和为16。

下面依次给出几个不同实现算法

int MaxSubseqSum1( int A[], int N )//算法1  T( N ) = O( N3 )
{
    int ThisSum, MaxSum = 0;
    int i, j, k;
    for( i = 0; i < N; i++ )   /* i是子列左端位置*/
    {
        for( j = i; j < N; j++ )   /* j是子列右端位置*/
        {
            ThisSum = 0; /* ThisSum是从A[i]到A[j]的子列和*/
            for( k = i; k <= j; k++ )
                ThisSum += A[k];
            if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大*/
                MaxSum = ThisSum; /* 则更新结果*/
        } /* j循环结束*/
    } /* i循环结束*/
    return MaxSum;
}

int MaxSubseqSum2( int A[], int N )  //算法2T( N ) = O( N2 )
{
    int ThisSum, MaxSum = 0;
    i【本文来自鸿网互联 (http://www.68idc.cn)】nt i, j;
    for( i = 0; i < N; i++ )   /* i是子列左端位置*/
    {
        ThisSum = 0; /* ThisSum是从A[i]到A[j]的子列和*/
        for( j = i; j < N; j++ )   /* j是子列右端位置*/
        {
            ThisSum += A[j];
            /*对于相同的i,不同的j,只要在j-1次循环的基础上累加1项即可*/
            if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大*/
                MaxSum = ThisSum; /* 则更新结果*/
        } /* j循环结束*/
    } /* i循环结束*/
    return MaxSum;
}
 
 int MaxSubseqSum4( int A[], int N ) //算法4T( N ) = O( N2 )
{
    int ThisSum, MaxSum;
    int i;
    ThisSum = MaxSum = 0;
    for( i = 0; i < N; i++ )
    {
        ThisSum += A[i]; /* 向右累加*/
        if( ThisSum > MaxSum )
            MaxSum = ThisSum; /* 发现更大和则更新当前结果*/
        else if( ThisSum < 0 ) /* 如果当前子列和为负*/
            ThisSum = 0; /* 则不可能使后面的部分和增大,抛弃之*/
    }
    return MaxSum;
}//&ldquo;在线&rdquo;的意思是指每输入一个数据就进行即时处理,在任 何一个地方中止输入,算法都能正确给出当前的解。

算法3---分治法

\

\

声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
MySQLと他のSQL方言の構文の違いは何ですか?MySQLと他のSQL方言の構文の違いは何ですか?Apr 27, 2025 am 12:26 AM

MySQLdiffersfromotherSQLdialectsinsyntaxforLIMIT,auto-increment,stringcomparison,subqueries,andperformanceanalysis.1)MySQLusesLIMIT,whileSQLServerusesTOPandOracleusesROWNUM.2)MySQL'sAUTO_INCREMENTcontrastswithPostgreSQL'sSERIALandOracle'ssequenceandt

MySQLパーティションは何ですか?MySQLパーティションは何ですか?Apr 27, 2025 am 12:23 AM

MySQLパーティション化により、パフォーマンスが向上し、メンテナンスが簡素化されます。 1)大きなテーブルを特定の基準(日付範囲など)、2)物理的に独立したファイルに物理的に分割する、3)MySQLはクエリするときに関連するパーティションに焦点を合わせることができます。

MySQLで特権をどのように許可して取り消しますか?MySQLで特権をどのように許可して取り消しますか?Apr 27, 2025 am 12:21 AM

mysqlで許可を許可および取り消す方法は? 1。grantallprivilegesondatabase_name.to'username'@'host 'などの許可を付与するために付与ステートメントを使用してください。 2。Revokeallprivilegesondatabase_name.from'username'@'host 'など、Revoke Statementを使用して、許可のタイムリーな通信を確保します。

InnoDBとMyisamストレージエンジンの違いを説明してください。InnoDBとMyisamストレージエンジンの違いを説明してください。Apr 27, 2025 am 12:20 AM

INNODBは、トランザクションサポートと高い並行性を必要とするアプリケーションに適していますが、Myisamはより多くの読み取りとより少ない書き込みを必要とするアプリケーションに適しています。 1.INNODBは、eコマースおよび銀行システムに適したトランザクションおよび銀行レベルのロックをサポートしています。 2. Myisamは、ブログやコンテンツ管理システムに適した、迅速な読み取りとインデックス作成を提供します。

MySQLの結合のさまざまなタイプは何ですか?MySQLの結合のさまざまなタイプは何ですか?Apr 27, 2025 am 12:13 AM

MySQLには4つのメイン結合タイプがあります:innerjoin、leftjoin、rightjoin、fullouterjoin。 1.InnerJoinは、結合条件を満たす2つのテーブルのすべての行を返します。 2.右のテーブルに一致する行がない場合でも、Leftjoinは左のテーブルのすべての行を返します。 3。右joinはleftjoinに反しており、右のテーブルのすべての行を返します。 4.fullouterjoinは、結合条件を満たしている、または満たさない2つのテーブルのすべての行を返します。

MySQLで利用可能なさまざまなストレージエンジンは何ですか?MySQLで利用可能なさまざまなストレージエンジンは何ですか?Apr 26, 2025 am 12:27 AM

mysqloffersvariousstorageEngines、それぞれのfordifferentusecases:1)Innodbisidealforapplicationsingingidcomplianceanceandhighconcurrency、support transactions andforeignkeys.2)myisamisbestforread-havyworkloads、transactionsupptort.3)

MySQLの一般的なセキュリティの脆弱性は何ですか?MySQLの一般的なセキュリティの脆弱性は何ですか?Apr 26, 2025 am 12:27 AM

MySQLの一般的なセキュリティの脆弱性には、SQLインジェクション、弱いパスワード、不適切な許可構成、および非合事ソフトウェアが含まれます。 1。SQL注射は、前処理ステートメントを使用することで防ぐことができます。 2。強力なパスワード戦略を強制的に使用することにより、弱いパスワードを回避できます。 3.不適切な許可構成は、ユーザー許可の定期的なレビューと調整を通じて解決できます。 4.未使用のソフトウェアは、MySQLバージョンを定期的にチェックして更新することでパッチを適用できます。

MySQLでスロークエリをどのように識別できますか?MySQLでスロークエリをどのように識別できますか?Apr 26, 2025 am 12:15 AM

MySQLの遅いクエリを識別することは、遅いクエリログを有効にし、しきい値を設定することで実現できます。 1.スロークエリログを有効にし、しきい値を設定します。 2.スロークエリログファイルを表示および分析し、詳細な分析のためにMySQLDumpSlowやPT-Query-Digestなどのツールを使用します。 3.インデックスの最適化、クエリの書き換え、およびselect*の使用を回避することで、遅いクエリの最適化を実現できます。

See all articles

ホット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衣類リムーバー

Video Face Swap

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

mPDF

mPDF

mPDF は、UTF-8 でエンコードされた HTML から PDF ファイルを生成できる PHP ライブラリです。オリジナルの作者である Ian Back は、Web サイトから「オンザフライ」で PDF ファイルを出力し、さまざまな言語を処理するために mPDF を作成しました。 HTML2FPDF などのオリジナルのスクリプトよりも遅く、Unicode フォントを使用すると生成されるファイルが大きくなりますが、CSS スタイルなどをサポートし、多くの機能強化が施されています。 RTL (アラビア語とヘブライ語) や CJK (中国語、日本語、韓国語) を含むほぼすべての言語をサポートします。ネストされたブロックレベル要素 (P、DIV など) をサポートします。

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

MantisBT

MantisBT

Mantis は、製品の欠陥追跡を支援するために設計された、導入が簡単な Web ベースの欠陥追跡ツールです。 PHP、MySQL、Web サーバーが必要です。デモおよびホスティング サービスをチェックしてください。

SecLists

SecLists

SecLists は、セキュリティ テスターの究極の相棒です。これは、セキュリティ評価中に頻繁に使用されるさまざまな種類のリストを 1 か所にまとめたものです。 SecLists は、セキュリティ テスターが必要とする可能性のあるすべてのリストを便利に提供することで、セキュリティ テストをより効率的かつ生産的にするのに役立ちます。リストの種類には、ユーザー名、パスワード、URL、ファジング ペイロード、機密データ パターン、Web シェルなどが含まれます。テスターはこのリポジトリを新しいテスト マシンにプルするだけで、必要なあらゆる種類のリストにアクセスできるようになります。