алгоритм Кадане в Java

Question

У меня есть следующая реализация алгоритма Кадане в Java.В основном, это найти максимальную сумму смежных подмассивов.

String[] numbers = string.split(",");
                int max_so_far = 0;
                int max_ending_here = 0;
                for (int i = 0; i < numbers.length-1;i++){
                     max_ending_here = max_ending_here + Integer.parseInt(numbers[i]);
                     if (max_ending_here < 0)
                         max_ending_here = 0;
                     if (max_so_far < max_ending_here)
                          max_so_far = max_ending_here;
                }
                System.out.println(max_so_far);

Однако это не сработает, если в массиве есть комбинация отрицательного и положительного числа, например:

2,3,-2,-1,10

Что должно возвращать 12 как максимум.На данный момент возвращается 5

Answer 1

Ваша реализация алгоритма выглядит нормально, но ваш цикл условный i < numbers.length-1 этого не делает: он останавливается всего в 1 последовательности от конца массива. i < numbers.length должен это сделать: -)

Answer 2

это работает для меня:

    String string = "2,3,-2,-1,10";
    String[] numbers = string.split(",");
    int max_so_far = 0;
    int max_ending_here = 0;
    for (String num : numbers) {
        int x = Integer.parseInt(num);
        max_ending_here = Math.max(0, max_ending_here + x);
        max_so_far = Math.max(max_so_far, max_ending_here);
    }
    System.out.println(max_so_far);

Answer 3

Относительно приведенного выше ответа Михала Шрайера:

Строка № 7: max_ending_here = Math.max (0, max_ending_here + x);

должно быть:

max_ending_here = Math.max (x, max_ending_here + x);

... в соответствии с алгоритмом Кадане, как определено здесь

Answer 4

Слишком поздно, но если кому-то это понадобится в будущем.

public static void kadaneAlgo(int[][] array)
    for(int i = 1; i < array.length; i++){
            int max_value_index_i = numberOrSum(array[i], past);
            if(max_value_index_i > sum){
                sum = max_value_index_i;
            }
            past = max_value_index_i;

        }
        System.out.println("Max sum from a contiguous sub array is : " + sum);
    }

    public static int numberOrSum(int number, int past){
        return Math.max(number, number+past);
    }