Матрица поиска максимальной суммы путем удаления почти одной строки или почти одного столбца

Question

Учитывая матрицу с m-строками и n-столбцами, нахождение максимальной суммы элементов в матрице путем удаления почти одной строки или одного столбца

Example: 
m=2, n=3

matrix : 
**[[1,2,-3]
[4,5,-6 ]
]**

вывод: 12, удалив третий столбец, затем сумму элементов в
[[1,2] [4,5]]

Как решить эту проблему в java8 с помощью динамического программирования

Answer 1

На основе алгоритма Кадане, приведенный ниже код работает нормально

public static void main(String[] args) {
    int[][] m = {
            {1, 2, -3},
            {4, 5, -5},
    };
    int N = m.length;

    for (int i = 0; i < N; ++i)
        m[0][i] = m[0][i];
    for (int j = 1; j < N; ++j)
        for (int i = 0; i < N; ++i)
            m[j][i] = m[j][i] + m[j - 1][i];

    int totalMaxSum = 0, sum;
    for (int i = 0; i < N; ++i) {
        for (int k = i; k < N; ++k) {
            sum = 0;
            for (int j = 0; j < N; j++) {
                sum += i == 0 ? m[k][j] : m[k][j] - m[i - 1][j];
                totalMaxSum = Math.max(sum, totalMaxSum);
            }
        }
    }

    System.out.println(totalMaxSum);
}