以下を中国語に翻訳してください: 配列から選択された数値の合計が空になるように最大化します

配列を取得し、そこから要素を選択し、その要素を合計に追加します。この要素を合計に追加した後、配列から 3 つの要素 (現在の番号、現在の番号 -1、存在する場合は現在の番号 1) を削除する必要があります。このメソッドでは、配列を空にして合計を取得します。最後に、合計を最大化する必要があります。

リーリー

イラスト

最初に、1、2、または 3 を削除する 3 つのステップがあります。

• 1 を削除してから、0、1、2 を削除する必要があります (これらのいずれかが存在する場合は、少なくとも 1 つが存在する必要があります)。合計は 1 になり、配列には 3 だけが残ります。 3 を削除すると、合計は 4 になります。

• 2 を削除してから、1、2、3 を削除する必要があり、最終的な合計は 2 になります。

• 最初に 3 を削除すると、合計は 3 になり、配列は 1 になります。 1を引くと合計は4になります。

リーリー

最初の 2 つの 3 を削除すると 6 が得られ、その後 2 つの 2 が削除されます。

その後、残りの 2 つのうち 1 つを削除し、答えとして 8 を取得します。

方法1

このメソッドでは、まず配列内に存在する最大要素を取得して、配列内に存在する要素の頻度を取得します。

後で、指定された配列に存在する要素の頻度を保存する配列を作成します。

周波数配列の最後の要素からトラバースを開始します。現在の 1 つのマイナス要素と 1 つのプラス要素を配列から削除する必要があるため、常にそれより 1 大きい数値が保持され、最大合計が得られます。 。

＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

時間と空間の複雑さ

上記のコードの時間計算量は O(N) です。ここで、N は指定された配列内に存在する最大の要素です。

上記のコードの空間計算量は時間計算量と同じで、要素の頻度を格納する配列を作成するため、両方とも O(N) です。

前述の方法には問題があります。最大の要素が非常に大きい場合、問題を解決するには多くの時間とスペースが必要になります。この問題を解決するには、次の方法があります。

マップメソッド

このアプローチでは、配列の代わりに要素の頻度を保存するマップを作成します。考え方は同じです。

＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

時間と空間の複雑さ

上記のコードの時間計算量は O(N) です。ここで、N は指定された配列に存在する要素の数です。

上記のコードの空間計算量は時間計算量と同じで、O(N) になります。これは、要素の頻度を保存するマップを作成するためです。

＃＃＃結論は＃＃＃

このチュートリアルでは、配列内の選択された数値の合計を最大化し、配列を空にする C プログラムを実装しました。そこから要素を選択し、その要素を合計に追加する必要があります。この要素を合計に追加した後、現在の番号、現在の番号 -1、および現在の番号 1 がある場合は、配列から 3 つの要素を削除する必要があります。時間と空間の線形複雑さを備えた 2 つの周波数ベースの方法を実装しました。

以上が以下を中国語に翻訳してください: 配列から選択された数値の合計が空になるように最大化しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。