私はグレート・マトリックスです

1975年。最大行列合計

難易度: 中

トピック: 配列、貪欲、行列

n x n の整数行列が与えられます。次の操作は何度でも実行できます:

• 行列の 隣接する要素を 2 つ選択し、それぞれに -1 を 乗算します。

2 つの要素は、境界を共有する場合にのみ、隣接とみなされます。

あなたの目標は、行列の要素の合計を最大化することです。上記の演算を使用して、行列の要素の 最大 合計を返します。

例 1:

• 入力: 行列 = [[1,-1],[-1,1]]
• 出力: 4
• 説明: 合計が 4 になるようにするには、次の手順に従います。
  • 最初の行の 2 つの要素に -1 を掛けます。
  • 最初の列の 2 つの要素に -1 を掛けます。

例 2:

• 入力: 行列 = [[1,2,3],[-1,-2,-3],[1,2,3]]
• 出力: 16
• 説明: 合計が 16 になるようにするには、次の手順に従います。
  • 2 行目の最後の 2 つの要素に -1 を掛けます。

制約:

• n == 行列.長さ == 行列[i].長さ
• 2
• -10⁵ <= 行列[i][j] <= 10⁵

ヒント:

1. 各行に負の数が 1 つだけ含まれるように演算を使用してみてください。
2. ネガティブな要素が 1 つしかない場合、それをポジティブに変換することはできません。

解決策:

この演算を使用して行列の合計を最大化するには、合計に対する負の寄与の絶対値を最小化する必要があります。計画は次のとおりです:

1. 負の数を数える: 行列内に存在する負の数の数を追跡します。
2. 最小絶対値の検索: 行列内の最小の絶対値を決定します。これは、負の数が奇数の場合に役立ちます。
3. 奇数の負の値を調整: 負の数のカウントが奇数の場合、最小の絶対値を正に反転することはできないため、可能な合計の最大値が制限されます。

このソリューションを PHP で実装してみましょう: 1975。最大行列合計

  
  
  説明：




絶対値の合計: 最適な構成では、可能な限り多くの負の数値が正の数値に反転されるため、すべての要素の絶対値の合計を計算します。

最小絶対値の追跡: 負の数のカウントが奇数である場合に、これを使用して合計を調整します。

奇数のネガティブの処理: ネガティブを完全に中和できない場合、避けられないネガティブな要素を考慮して、合計から最小の絶対値を 2 倍引きます。



  
  
  複雑




時間計算量: O(n^2)、行列が 1 回走査されるため。

空間の複雑さ: O(1)。変数以外に追加の空間は使用されないためです。


このソリューションは、指定された制約内で効率的に機能します。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:


LinkedIn
GitHub



          

            
  

            
        
以上が私はグレート・マトリックスですの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。