貪欲アルゴリズム: K回の反転後の配列の合計を最大化する

[[355496]]

多くのレコーディング仲間が、昨日のトピック「貪欲アルゴリズム：ジャンピングゲーム II」は難しいと報告しています。これでほっとしました。笑。ちょうど貪欲を説明していたとき、何人かのレコーディング仲間が「貪欲を別途説明する必要はなく、動作ルールを直接説明すればいい」と提案してくれたからです。多くの学生は、それは単なる欲張りで、難しいことではないと感じるかもしれません。貪欲の原理は単純ですが、問題の解決方法は非常に巧妙で、難易度はルールとそれほど変わらないことがわかります。

今日は簡単な質問です。鍵となるのは、貪欲な問題解決の考え方を養うことです。

K 回の否定後の配列の合計を最大化し、問題のアドレス: https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/

整数の配列 A が与えられた場合、配列を変更する方法は次のとおりです。インデックス i を選択し、A[i] を -A[i] に置き換え、このプロセスを合計 K 回繰り返します。 (同じインデックス i を複数回選択できます。)

このように配列を変更すると、配列の最大可能合計が返されます。

例1: 入力: A = [4,2,3]、K = 1

出力: 5

説明: インデックス (1,) を選択すると、A は [4,-2,3] になります。

例2:

入力: A = [3,-1,0,2]、K = 3

出力: 6

説明: インデックス (1, 2, 2) を選択すると、A は [3,1,0,2] になります。

例3:

入力: A = [2,-3,-1,5,-4]、K = 2

出力: 13

説明: インデックス (1, 4) を選択すると、A は [2,3,-1,5,4] になります。

ヒント：

1 <= A.長さ <= 10000
1 <= K <= 10000
-100 <= A[i] <= 100

アイデア

この質問のアイデアは、実は非常に簡単に考えることができます。配列の合計を最大化するにはどうすればよいでしょうか?

貪欲な思考、局所最適性: 絶対値の大きい負の数を正の数に変換し、現在の値を最大化します。全体的な最適性: 配列全体の合計が最大に達します。

局所最適は全体最適につながる可能性があります。

したがって、すべての負の数を正の数に変換しても、K は依然として 0 より大きくなります。このときの問題は、正の整数の順序付けられたシーケンスであることです。正の数と負の数を K 回変換して、配列の合計を最大化する方法。

次に、別の貪欲なソリューションがあります。ローカル最適ソリューション: 反転する最小の正の整数のみを見つけて、現在の値が最大値に達するようにします (たとえば、正の整数配列 {5, 3, 1} では、1 を反転して -1 を取得することは、5 を反転して -5 を取得するよりもはるかに大きくなります)。グローバル最適ソリューション: 配列全体の合計が最大値に達します。

この問題を解くときに貪欲アルゴリズムについて考えないかもしれませんが、AC を 1 回で取得できます。

「実は、私は見落とされがちな貪欲な思考をお見せするためにここにいます。こんなに単純な問題に、貪欲な思考を 2 回も使いました!」

この問題を解決するための手順は次のとおりです。

ステップ 1: 配列を絶対値に従って最大から最小の順に並べ替えます。「絶対値に従って並べ替える必要があることに注意してください」
ステップ2: 前から後ろへ移動し、負の数に遭遇したら正の数に変換し、K--
ステップ3: Kがまだ0より大きい場合は、Kが使い果たされるまで、最小値を持つ要素を繰り返し変換します。
ステップ4: 合計

対応する C++ コードは次のとおりです。

クラスソリューション{
静的ブールcmp( int a, int b) {
戻る 絶対値(a) >絶対値(b)
 }
公共：
 int largestSumAfterKNegations(ベクトル< int >& A, int K) {
        sort( A.begin (), A.end ( ), cmp); // 最初のステップ
for ( int i = 0; i < A.size ( ); i++) { // ステップ2
            もし (A[i] < 0 && K > 0) {
                A[i] * = -1;
                K --;  
            }
        }
        while (K --) A[A.size() - 1] *= -1; // ステップ3  
 int結果 = 0;
 for ( int a : A) result += a; // ステップ4
結果を返します。
    }
 };