输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有子数组的和的最大值,要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2, 因此输出为该子数组的和18。

思路

定义两个临时变量,一个为当前最大求和值,另一个为最大求和值(初始化为数组第一个元素)。即:

int currSum = 0;
int maxSum = a[0];       //全负情况,返回最大数

循环给定数组,如果当前索引值 > 当前值与当前索引数值的和,则将当前索引值赋值给 currSum,否则将和赋给 currSum。比较 maxSum 和 currSum 的值,将大的值赋给 maxSum:

    public int maxSubArray(int[] a, int n) {
        int currSum = 0;
        int maxSum = a[0];       //全负情况,返回最大数
        System.out.println("a[j]" + "   " + "currSum" + "   " + "maxSum");
        for (int j = 0; j < n; j++) {
            System.out.println(a[j] + "        " + currSum + "        " + maxSum);
            currSum = (a[j] > currSum + a[j]) ? a[j] : currSum + a[j];
            maxSum = (maxSum > currSum) ? maxSum : currSum;

        }
        return maxSum;
    }

测试

@Test
    public void testMaxSubArray() {
        int[] in = new int[]{1, -2, 3, 10, -4, 7, 2, -5};
        System.out.println(maxSubArray(in, in.length));
    }

输出

a[j]   currSum   maxSum
1        0        1
5        1        1
8        6        6
2        14        14
1        16        16
3        17        17
9        20        20
4        29        29
33


原文:https://wizardforcel.gitbooks.io/the-art-of-programming-by-july/content/02.04.html