Оптимизация кода C++

Question

Очень многие тестирующие системы устанавливают максимальное время работы кода, моя история как раз об этом. Код не проходит на последнем тесте из-за превышения времени работы (дольше 1 сек). Задача такая: Вход : массив из чисел Вывод: массив, где каждый i,j элемент - это сумма всех элементов до ij-го введенного массива. Пример:

Выход

1 3 6
5 12 21

Мой кусочек кода:

    for (long int i = 0; i < array.rows; i++) {
        for (long int j = 0; j < array.cols; j++) {
            cin >> input;
            array.data[i][j] = input;
            long int k = 0;
            for (long int t = 0; t <= i; t++) {
                for (long int l = 0; l <= j; l++) {
                    k += array.data[t][l];
                }
            }
            cout << k << ' ';
        }
        cout << endl;
    }

Есть ли идеи, как ускорить?

Answer 1

Код переведён с Питона отсюда, работает за n^2 (количество элементов в матрице).

Исходные данные в a[][], кумулятивные суммы в cs[][] такой же размерности. Если новый массив не требуется, а исходные данные сохранять не нужно, то вычисления можно производить внутри того же a[][].

Копируется первая строка, затем делается один проход с вычислением сумм по столбцам, затем проход с вычислением по строкам.

for (int c = 0; c < a.cols; c++)
    cs[0][c] = a[0][c];

for (int r = 1; r < a.rows; r++)
    for (int c = 0; c < a.cols; c++)
        cs[r][c] = cs[r-1][c] + a[r][c];

 for (int r = 0; r < a.rows; r++)
     for (int c = 1; c < a.cols; c++)
         cs[r][c] += cs[r][c-1];

Answer 2

Проблема в том, что ваше решение пересчитывает каждый раз заново всю сумму элементов, что приводит к ужасной асимптотике в О(n^4). Эту задачу можно решить с помощью динамического программирования. Для этого подумайте, как можно получить ответ для i,j за O(1) из уже имеющихся данных, а не за О(n^2) циклами.

Небольшая подсказка: пусть d - искомый массив. Как узнать d[i][j] зная значения a[i][j], d[i-1][j-1], d[i-1][j] и d[i][j-1]?

Это решение также позволяет помимо оптимизации времени работы до О(n^2) оптимизировать память до O(n) если заметить, что мы всегда работаем только с двумя строками массива d: текущей и предыдущей.

БЛОГ НА HUSL

Оптимизация кода C++

Ответы (2 шт):