Максимальная проблема подрешетки сложная перебор

Question

Какова сложность времени выполнения / памяти для задачи Максимальный подмассив с использованием грубой силы?

Могут ли они быть оптимизированы больше? Особенно сложность памяти?

Спасибо,

Answer 1

Грубая сила - Омега (n^2). Используя Разделяй и властвуй, вы можете делать это со сложностью Theta(n lg n). Дальнейшие подробности доступны во многих книгах, таких как Введение в алгоритмы, или в различных ресурсах в Интернете, таких как эта лекция.

Answer 2

Как предлагается в этом ответе, вы можете использовать алгоритм Кадане, который имеет сложность O(n). Реализация на Java:

public int[] kadanesAlgorithm (int[] array) {
        int start_old = 0;
        int start = 0;
        int end = 0;
        int found_max = 0;

        int max = array[0];

        for(int i = 0; i<array.length; i++) {
            max = Math.max(array[i], max + array[i]);
            found_max = Math.max(found_max, max);
            if(max < 0)
                start = i+1;
            else if(max == found_max) {
                start_old=start;
                end = i;
                }
        }

        return Arrays.copyOfRange(array, start_old, end+1);
    }