Алгоритм линейного времени для максимальной непрерывной суммы подмассива

Question

Я решал упражнение из Введение в алгоритмы - CLRS и наткнулся на решение максимального смежного подмассива за линейное время (Q 4.1-5). Пожалуйста, посмотрите на мое решение ниже. Я искал онлайн-судей для этого упражнения, но не нашел ни одного. Решив его, когда я искал решения, я нашел алгоритм Кадане, который кажется отличным от моей реализации, и это решение дает правильный вывод, когда все числа отрицательны.

public static int linearMaxSolve(int[] arr) {
int max = Integer.MIN_VALUE;
int sum = 0;
for (int i : arr) {
    sum += i;
    if (i > sum) {
        sum = i;
    }
    if (sum > max) {
        max = sum;
    }
}
return max;
}

Есть ли способ проверить правильность этого алгоритма, кроме подачи в программу тестовых примеров вручную?

Answer 1

Это действительно зависит от того, как вы определяете массив со всеми отрицательными значениями.

Если вы не считаете пустой под-массив возможным решением, тогда да, ваше решение правильное и фактически оно точно такое же, как алгоритм Кадане.

int max_so_far = a[0];
int max_ending_here = a[0];

for (int i = 1; i < size; i++)
{
    max_ending_here = Math.max(a[i], max_ending_here+a[i]);
    max_so_far = Math.max(max_so_far, max_ending_here);
}
return max_so_far;

Единственная разница заключается в инициализации, но если вы внимательно посмотрите, на первой итерации вашего алгоритма, оба sum а также max будет иметь значение a[0],

Но опять же, вы предполагаете, что оба ваших массива не пустые (в этом случае вы вернетесь Integer.MIN_VALUE, это то, что вы хотите?) и что пустой подмассив (сумма ==0) не является возможным решением.