题目描述

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

示例：

 输入：[1,-2,3,10,-4,7,2,-5]
输出：18
对应子数组：[3,10，-4，7，2]  

解题分析

这道题可以使用动态规划来解决，先求解子问题的最优解，再构造原问题的最优解。解题思路是将数组的值修改为子序列的最大值。

从前往后遍历，最大的连续子序列的和是由当前元素和之前的最大连续子序列的和叠加在一起形成的。如果之前的最大连续子序列的和大于零，我们可以继续累加。如果小于零，则需要舍去之前的子序列，重新从当前的数字开始累加。

时间复杂度为：

实现代码

 public int FindGreatestSumOfSubArray(int[] array) {
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        array[i] += array[i - 1] > 0 ? array[i - 1] : 0;
        max = Math.max(max, array[i]);
    }
    return max;
}  

如果您喜欢这篇文章，辛苦留言、点赞、关注~~~