42.连续子数组的最大和

raylan.chen大约 2 分钟

class Solution {
    public int maxSales(int[] sales) {
        int[] dp = new int[sales.length];
        dp[0] = sales[0];
        int max = sales[0];
        for (int i = 1; i < sales.length; i++){
            int tmp = dp[i - 1] + sales[i];
            if (tmp >= sales[i]) dp[i] = tmp;
            else dp[i] = sales[i];
            if (dp[i] > max) max = dp[i];
        }
        return max;
    }
}

参照题解，可以将 for 循环里面的语句优化

class Solution {
    public int maxSales(int[] sales) {
        int[] dp = new int[sales.length];
        dp[0] = sales[0];
        int max = sales[0];
        for (int i = 1; i < sales.length; i++){
            dp[i] = sales[i] + ((dp[i - 1] >= 0) ? dp[i - 1] : 0);

            if (dp[i] > max) max = dp[i];
        }
        return max;
    }
}

优秀题解

class Solution {
    public int maxSales(int[] sales) {
        int res = sales[0];
        for(int i = 1; i < sales.length; i++) {
            sales[i] += Math.max(sales[i - 1], 0);
            res = Math.max(res, sales[i]);
        }
        return res;
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solutions/151339/mian-shi-ti-42-lian-xu-zi-shu-zu-de-zui-da-he-do-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

dp[i] ：

包含 sales[i] 元素的连续子数组的最大和

虽然 sales[i] 有时候会为负数，但是有时免不了通过负数来联结下一个正数来使得连续子数组的最大和增加

转移方程：

需要判断 dp[i - 1] 对 dp[i] 所做的贡献

判断是否要与前元素组成连续子数组来追求最大和，还是自己单干会使得最大和显得更好些

42.连续子数组的最大和

42.连续子数组的最大和

参考链接

个人尝试

优秀题解