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

Я решал упражнение из Introduction to Algorithms — 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;
}

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


java algorithm kadanes-algorithm
person Hiresh    schedule 11.03.2018    source источник
comment
Так в чем твой вопрос?   -  person TeaCoder    schedule 11.03.2018
comment
Обратите внимание, что Stack Overflow не является дискуссионным форумом. (со страницы tour) Итак, задайте вопрос, пожалуйста.   -  person user202729    schedule 11.03.2018
comment
Можно спорить, каков правильный вывод, если все элементы массива отрицательные. Один из возможных ответов — 0 (для пустого подмассива).   -  person Henry    schedule 11.03.2018

Ответы (1)


arrow_upward
4
arrow_downward

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

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

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, это то, что вы хотите?), и что пустой подмассив (sum==0) не является возможным решением.

person A. Sarid    schedule 11.03.2018