C语言——求矩阵中不同行不同列的两个数的最大乘积

小灰灰 2022-12-06 05:27 186阅读 0赞

> 刚刚做的一个笔试题，记录一下

题目描述：一个n\*m的矩阵，求其中不同行并且不同列的两个数的最大乘积。2=<n,m<=1000.

如矩阵：

1 2 8

4 3 6

5 4 1

输入：第一行输入矩阵的行数n和列数 m

在输入n行，每行m个元素

输出：该数组不同行不同列两个数的最大乘积

思路：一开始拿到题我想到的是用两个二维数组进行两两相乘，后来发现时间复杂度太高了。在仔细读题，可以发现我们可以将每行最大值和次大值保存下来，最大值一定是由某行的最大值或次大值乘以另一行最大值或次大值。

对第i行和第j行来说；

如果两者最大值maxi和maxj对应的列下标不相同，则max=maxi\*maxj

如果两者最大值maxi和maxj对应的列下标相同，则max=maxi\*secMaxj 或者max=secMaxi\*maxj

#include<stdio.h>
    int max(int a, int b)
    {
        int max = a;
        if (b > max)
            max = b;
        return max;
    }
    int main()
    {
    
        int n, m, arr[1000][1000];
        while (scanf("%d %d", &n, &m) != EOF)
        {
            int M[1000] = { 0 };
            int col[1000];
            int sec[1000];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                {
                    scanf("%d", &arr[i][j]);
                    if (arr[i][j] > M[i])
                    {
                        sec[i] = M[i];//更新次大值
                        M[i] = arr[i][j];//更新最大值
                        col[i] = j;
                    }
                    else if (arr[i][j] > sec[i])
                    {
                        sec[i] = arr[i][j];//比最大值小但比次大值大，更新次大值
                    }
                }
            int val = 1;
            for(int i=0;i<n;i++)
                for (int j = i + 1; j <= n; j++)
                {
                    if (col[i] != col[j])//第i行最大值对应的列不等于第j行最大值对应的列
                        val = max(val, M[i] * M[j]);
                    else
                    {
                        val = max(val, M[i] * sec[j]);
                        val = max(val, M[j] * sec[i]);
                    }
    
                }
            printf("%d\n", val);
        }
    
    
    }