algorithm - 最大子阵列问题蛮力复杂度

Question

使用蛮力的最大子数组问题的运行时/内存复杂度是多少？

它们可以进一步优化吗？尤其是内存复杂度？

谢谢，

Answer 1

蛮力是 Omega(n^2)。使用分而治之，您可以使用 Theta(n lg n) 复杂性来做到这一点。更多详细信息可在许多书籍（例如Introduction to Algorithms）或 Web 上的各种资源（例如本讲座）中找到。

Answer 2

正如这个答案中所建议的，您可以使用具有 O(n) 复杂度的 Kadane 算法。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);
    }