データ構造とアルゴリズム: K 回の否定後の配列の合計を最大化する

[[435915]]

K回の反転後の配列の最大合計

LeetCode の問題へのリンク: 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 --;  
            }
        }
        if (K % 2 == 1) A[ A.size () - 1] *= -1; // ステップ3
 int結果 = 0;
 for ( int a : A) result += a; // ステップ4
結果を返します。
    }
 };

要約する

貪欲問題が単純化されると、人々は疑問を抱き始めます。「これはこのように行われるべきではないのか？これもアルゴリズムなのか？これは貪欲ではないと思う。」

この問題は実は非常に単純で、貪欲アルゴリズムを知らない人でも解くことができますが、ここでは貪欲アプローチを使用して全体を通して説明します。

欲深い考えは必ず存在するからです！

貪欲な考え方（局所最適、大域最適）を持っていない場合、単純な貪欲な質問を感情に基づいて行い、難しい貪欲な質問をまったく解けないという罠に陥りやすくなります。実際、これでは貪欲な考え方を訓練することはできません。

したがって、たとえそれが貪欲な単純な質問だとわかっていても、それを解くには貪欲な思考に頼らなければなりません。これは問題解決の感覚を養うのに非常に役立ちます。

その他の言語

ジャワ

クラスソリューション{
公共  int largestSumAfterKNegations( int [] nums, int K) {
     // 配列を絶対値に従って最大から最小の順に並べ替えます。順序は絶対値に基づく必要があることに注意してください。
 nums = IntStream.of (nums )です。
       .ボックス化()
       .sorted((o1, o2) -> Math.abs (o2) - Math.abs ( o1))
       .mapToInt(整数:: intValue ).toArray();
 int len = nums.length;
 ( int i = 0; i < len; i++)の場合{
     //前から後ろへ走査し、負の数が見つかったら正の数に変換します。同時に、K --  
     （数値[i] < 0 && K > 0）の場合{
      数値[i] = -数値[i];
      K --;  
     }
 }
 // K がまだ 0 より大きい場合は、K が使い果たされるまで、最小値を持つ要素を繰り返し変換します。 
 
 K % 2 == 1の場合、nums[len - 1] = -nums[len - 1];
 Arrays.stream(nums).sum ( )を返します。 
 
    }
 }

クラスソリューション{
公共  int largestSumAfterKNegations( int [] A, int K) {
        A.length == 1の場合、 k % 2 == 0 ? A[0] : -A[0]を返します。
        配列.sort(A);
整数 合計= 0;
整数idx = 0;
 ( int i = 0; i < K; i++)の場合{
            (i < A.length - 1 && A[idx] < 0)の場合{
                A[idx] = -A[idx];
                A[idx] >= Math.abs (A[idx + 1]) の場合、idx++;
続く;
            }
            A[idx] = -A[idx];
        } 
 
 ( int i = 0; i < A.length; i++) {
合計+= A[i];
        }
戻る 合計;
    }
 }

パイソン

クラスソリューション:
    def largestSumAfterKNegations(self, A: List[ int ], K: int ) -> int :
        A = sorted(A, key = abs , reverse= True ) # A を絶対値で大きい順に並べ替える
iが範囲(len(A))内にある場合:
            K > 0かつA[i] < 0の場合:
                A[i] *= -1
                1 です
        K > 0の場合:
            A[-1] *= (-1)**K #Aの最後の数字を取得するには、-1と書くだけです
戻る 合計（A）

行く

関数 largestSumAfterKNegations(nums [] int , K int ) int {
 sort.Slice(nums, func(i, j int ) bool {
戻り値math.Abs ( float64(nums[i])) > math.Abs ( float64(nums[j]))
 }) 
 
 i := 0; i < len(nums); i++ {
  K > 0 && nums[i] < 0 の場合 {
   数値[i] = -数値[i]
   K --  
  }
 } 
 
 K%2 == 1 の場合 {
  nums[len(nums)-1] = -nums[len(nums)-1]
 } 
 
 結果:= 0
 i := 0; i < len(nums); i++ {
  結果 += 数値[i]
 }
結果を返す
}

ジャバスクリプト

var largestSumAfterKNegations =関数(nums, k) {
    nums.sort((a, b) => {
 Math.abs (b) - Math.abs ( a )を返す
    })
 ( i = 0 とします; i < nums.length; i++) {
        数値[i] < 0 && k > 0 の場合
            数値[i] *= -1
            か --  
        }
    } 
 
    k > 0 && k % 2 === 1 の場合
        数値[数値.長さ - 1] *= -1
    }
    0 = 0 です
 
 nums.reduce((a, b) => {を返す
a + bを返す
    })
 };