放置在矩阵上的两个非攻击车的最大平方和是多少？

Question

有一个 m x n 矩阵，每个矩阵都有整数元素。问题是我们必须在该矩阵上放置两个车，这样它们就不会互相攻击，并且放置车的元素之和最大。

示例： 假设矩阵是

2 5
1 3

那么非攻击车只能放置在 2,3 或 1,5 元素位置上。但在 1,5 的情况下找到最大总和，因此该函数应返回 1 + 5 = 6。

我认为我们可以一一遍历数组的所有对，然后返回我们找到的最大总和，但我似乎找不到更好或更有效的方法。就复杂性而言，我的解决方案是

O(m * m * n * n)

。

更好的方法是什么？我将不胜感激任何帮助。

Answer 1

1. 对于每一行，找到前 2 个值并记住找到它们的列。 O(百万)

2. 对于每一列，找到前 2 个值并记住找到它们的行。 O(百万)

3. 剩下的操作，我们只使用上面构建的两个列表。我们不会再看矩阵了：

   1. 对于每一行，假装在该行和具有最高值的列中放置一个车。对于每一列，将顶部值与该列的顶部值相加，但车所在的列除外，我们在该列中与第二高值相加。记住假装车所在的行和总和最高的列。 O(百万)

   2. 重复，但使用第二高的值。 O(百万)

操作完成。 O(mn) + O(mn) + O(mn) + O(mn) = O(mn)

Answer 2

基于上面的@Andreas评论，这里是代码：

int solution(vector<vector<int>>& board) {
    int n = board.size();
    int m = board[0].size();

    vector<vector<int>> row(n);
    vector<vector<int>> col(m);

    for (int i = 0 ; i < n ; i++) {
        int mx = 0  , mxc  , smx = 0  , smxc;
        for (int j = 0 ; j < m ; j++) {
            if (board[i][j] >= mx) {
                smx = mx ;
                smxc = mxc;

                mx = board[i][j];
                mxc = j;
            }
            else if (board[i][j] >= smx){
                smx = board[i][j];
                smxc = j;
            }
        }
        row[i].push_back(mxc);
        row[i].push_back(smxc);
    }
    for (int j = 0 ; j < m ; j++) {
        int mx = 0 , mxr  , smx = 0  , smxr ;
        for (int i = 0 ; i < n ; i++) {
            if (board[i][j] >= mx) {
                smx = mx ;
                smxr = mxr;

                mx = board[i][j];
                mxr = i;
            }
            else if (board[i][j] >= smx) {
                smx = board[i][j];
                smxr = i;
            }
        }
        col[j].push_back(mxr);
        col[j].push_back(smxr);
    }
    int ans = 0 ;
    for (int i = 0 ; i < n ; i++) {
        int r = i  , c =  row[i][0];
        for (int  j = 0 ; j < m ; j++) {
            if (j != c) {
                if (col[j][0] != r)
                    ans =  max(ans , board[r][c] + board[col[j][0]][j]);
                else
                    ans =  max(ans , board[r][c] + board[col[j][1]][j]);
            }
        }
    }
    for (int j = 0 ; j < m ; j++) {
        int c = j  , r = col[j][0];
        for (int i = 0 ; i < n ; i++) {
            if (i != r) {
                if (row[i][0] != c)
                    ans = max(ans , board[r][c] + board[i][row[i][0]]);
                else
                    ans = max(ans , board[r][c] + board[i][row[i][1]]);
            }
        }
    }
    return ans ;
}

Answer 3

我在 JavaScript 中尝试过这个。虽然这可能不是最有效的方法，但我愿意接受任何提高性能的建议。非常欢迎您的见解。

function solution(A) {
    let max = 0;
    let a = {};
    let b = [];

    for (let i = 0; i < A.length; i++) {
        for (let j = 0; j < A[i].length; j++) {
            a['' + i + j] = A[i][j];
            b.push([i, j]);
        }
    }

    for (let i = 0; i < b.length; i++) {
        for (let j = i + 1; j < b.length; j++) {
            let sum = a[b[i].join('')] + a[b[j].join('')];
            if (b[i][0] !== b[j][0] && b[i][1] !== b[j][1] && max < sum) {
                max = sum;
            }
        }
    }

    return max;
}

console.log(solution([[2, 4], [8, 5]]))

Answer 4

我从Andreas建议的算法开始，并对其进行了一些调整以进行微小的改进，如下面Andreas答案中的我的评论中所述。这是我想出的代码。我测试了它的准确性，但没有测试性能。

public static int solution(int[][] A) {

    int[][] rTop2 = new int[A.length][2];

    for (int i = 0; i < A.length; i++) {
        for (int j = 0; j < A[i].length; j++) {
            if (A[i][j] >= A[i][rTop2[i][1]] || rTop2[i][1]==rTop2[i][0]) {
                rTop2[i][1] = j;

                if (A[i][rTop2[i][1]] > A[i][rTop2[i][0]]) {

                    rTop2[i][0] += rTop2[i][1];
                    rTop2[i][1] = rTop2[i][0] - rTop2[i][1];
                    rTop2[i][0] = rTop2[i][0] - rTop2[i][1];
                }
            }
        }
    }

    int maxSum = 0;
    for (int i=0; i < rTop2.length; i++) {
        for (int s=0; s < 2; s++) {

            for (int j=i+1; j < rTop2.length; j++) {

                if (rTop2[j][0] == rTop2[i][s]) {
                    maxSum = Math.max(maxSum, (A[i][rTop2[i][s]] + A[j][rTop2[j][1]]));
                } else {
                    maxSum = Math.max(maxSum, (A[i][rTop2[i][s]] + A[j][rTop2[j][0]]));
                }
            }
        }
    }
    return maxSum;
}