【剑指Offer】连续子数组的最大和

Posted on | In ,

题目

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

举例分析数组的规律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int FindGreatestSumOfSubArray(int[] array) {
    if (array == null || array.length < 1)
        return 0;

    int max = Integer.MIN_VALUE;
    int sum = -1;

    for (int i = 0; i < array.length; i++) {
        if (sum < 0)
            sum = array[i];
        else
            sum += array[i];

        if (sum > max)
            max = sum;
    }

    return max;
}

应用动态规划法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int FindGreatestSumOfSubArray(int[] array) {
    if (array == null || array.length < 1)
        return 0;

    int max = Integer.MIN_VALUE;
    int[] s = new int[array.length];
    s[0] = array[0];

    for (int i = 1; i < s.length; i++) {
        s[i] = Math.max(array[i], s[i - 1] + array[i]);
        max = Math.max(s[i] , max);
    }

    return max;
}