42. 连续子数组的最大和

Leetcode

题目描述

{6, -3, -2, 7, -15, 1, 2, 2}，连续子数组的最大和为 8（从第 0 个开始，到第 3 个为止）。

解题思路

sum 表示以当前元素结尾的连续子数组的最大和。前面的 sum 小于等于 0 时，接上它只会让和变小，不如从当前元素重新开始；否则把当前元素接在后面。所有位置的 sum 中最大的就是答案，时间复杂度 O(N)，空间复杂度 O(1)。

val          6   -3   -2    7  -15    1    2    2
sum          6    3    1    8   -7    1    3    5
greatestSum  6    6    6    8    8    8    8    8

public int maxSales(int[] sales) {
    if (sales == null || sales.length == 0)
        return 0;
    int greatestSum = Integer.MIN_VALUE;
    int sum = 0;
    for (int val : sales) {
        sum = sum <= 0 ? val : sum + val;
        greatestSum = Math.max(greatestSum, sum);
    }
    return greatestSum;
}