C++程序 将所有行或所有列旋转以使矩阵对角线元素之和最大

C++程序 将所有行或所有列旋转以使矩阵对角线元素之和最大

给定一个尺寸为 N * N 的方阵 mat [] [] ,任务是通过将矩阵的所有行或所有列旋转正整数来查找可能从给定矩阵获得的对角线元素的最大和。

例:

输入: mat [][] = {{1,1,2},{2,1,2},{1,2,2}}

输出: 6

解释:

将矩阵的所有列旋转1会将mat [][ ]修改为{{2,1,2},{1,2,2},{1,1,2}}。

因此,矩阵的对角线元素之和= 2 + 2 + 2 = 6,这是最大的可能值。

输入: A [][] = {{-1,2},{-1,3}}

输出: 2

方法: 将矩阵的所有行和列在所有可能的方式中旋转,并计算所获得的最大和。按照以下步骤解决问题:

  • 初始化一个变量,称为 maxDiagonalSum ,以通过将矩阵的所有行或列旋转来存储矩阵对角线元素的最大可能和。
  • 将矩阵的所有行旋转正整数,范围为 [0,N – 1] ,并更新 maxDiagonalSum 的值。
  • 将矩阵的所有列旋转正整数,范围为 [0,N – 1] , 并更新 maxDiagonalSum 的值。
  • 最后,打印 maxDiagonalSum 的值。

下面是上述方法的实现:

// C ++程序来实现
//上述方法
  
#include <bits/stdc++.h>
using namespace std;
#define N 3
  
  
//函数,以通过旋转行或列找到矩阵对角线元素的最大和
int findMaximumDiagonalSumOMatrixf(int A [] [N])
{
      
      
    //存储矩阵对角线元素的最大和
    //通过旋转行或列
    int maxDiagonalSum = INT_MIN;
      
  
    //将所有列按整数旋转
    //在[0,N - 1]范围
    for(int i = 0; i < N; i ++){
          
  
        //存储矩阵的对角线元素之和
        //的矩阵
        int curr = 0;
          
  
        //计算矩阵的对角线
        //元素的总和
        for(int j = 0; j < N; j ++){
              
  
            //更新事实
            curr + = A [j] [(i + j)%N];
        }
          
          
        //更新maxDiagonalSum
        maxDiagonalSum = max(maxDiagonalSum,
curr);
    }
  
  
    //将所有行向正整数旋转
    //在[0,N - 1]范围内
    for(int i = 0; i < N; i ++){
          
  
        //存储矩阵的对角线元素之和
        //的矩阵
        int curr = 0;
          
  
        //计算矩阵的对角线
        //元素的总和
        for(int j = 0; j < N; j ++){
              
  
            //更新事实
            curr + = A [(i + j)%N] [j];
        }
          
          
        //更新maxDiagonalSum
        maxDiagonalSum = max(maxDiagonalSum,
                                      curr);
    }
  
        
    return maxDiagonalSum;
}
  
  
//驱动程序
int main()
{
      
    int mat [N] [N] = {{1,1,2},{2,1,2},{1,2,2}};
      
    cout << findMaximumDiagonalSumOMatrixf(mat);
    返回0;
} ```  

输出:

 6

时间复杂度: O(N 2 )

辅助空间: O(1)

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例