连续子数组的最大和

一、需求

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

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

二、暴力法

2.1 思路分析

当然了，暴力法不符合题意，但是也是最先想到的，既然想到了，那就把它实现出来吧；
具体注释写在代码上；

2.2 代码实现

class Solution {
    public int maxSubArray(int[] nums) {
        int res = Integer.MIN_VALUE;
        for(int i = 0; i < ; i++) {
            //这里直接将非正数略过
            if(nums[i] <= 0) continue;
            int temp = 0;
            for(int j = i; j < ; j++) {
                temp += nums[j];
                if(res < temp) res = temp;
            }
        }
        //sort默认升序排序，当数组中元素值全为零或负数时，需返回最大值
        (nums);
        return (nums[-1],res);
    }
}

2.3 复杂度分析

时间复杂度为O(N^2)，其中N为数组元素的个数；
空间复杂度为O(1)；

三、动态规划法1

3,1 思路分析

题目求的是连续子数组的最大和，看到涉及最大/最小值，尝试利用动态规划来解决；
既然是动态规划，那么就要定义状态，找状态方程以及给定状态初值；
定义状态：dp[i]表示以nums[i]为结尾的连续子数组的最大和；
状态方程：①dp[i-1] <= 0时，dp[i] = nums[i]，即起负(或无)作用就略过；②dp[i] > 0时，dp[i] = dp[i-1] + nums[i]；
状态初值：dp[0] = nums[0]，即以nums[0]为结尾的连续子数组的最大和；
返回值：返回dp数组中的最大值即可；

3.2 代码实现

class Solution {
    public int maxSubArray(int[] nums) {
        int i;
        int[] dp = new int[];
        dp[0] = nums[0];
        for(i = 1; i < ; i++) {
            if(dp[i-1] <= 0) {
                dp[i] = nums[i];
            } else {
                dp[i] = dp[i-1] + nums[i];
            }
        }
        (dp);
        return dp[-1];
    }
}

3.3 复杂度分析

时间复杂度为O(NlogN)，其中N为数组元素的个数；
空间复杂度为O(N)；

四、动态规划法2

4.1 思路分析

上面的时间复杂度为O(NlogN)，不符合题目要求的O(N)，因此需要进一步优化；
因为dp[i]只与dp[i-1]与nums[i]相关，因此考虑用数组nums作为dp列表，这样避免了申请空间；
上面的算法是求出了dp[0]~dp[-1]很多个值，这一次我们每求出一个就比较一次，最后只剩下一个最值；

4.2 代码实现

class Solution {
    public int maxSubArray(int[] nums) {
        //假定当前最大值的nums[0]
        int res = nums[0];
        for(int i = 1; i < ; i++) {
            //nums[i]>0则加，否则nums[i]保持不变
            nums[i] += (nums[i-1],0);
            //每求一次nums[i]，更新一次最值
            res = (res,nums[i]);
        }
        return res;
    }
}

4.3 复杂度分析

时间复杂度为O(N)，N为数组元素的个数；
空间复杂度为O(1)，使用常数大小的额外空间；

五、动态规划法3

5.1 思路分析

上面的代码已符合题目要求了，但是还可以继续优化，因为上面修改了原数组；
根据上面的思想，我们定义两个变量，一个pre用来表示dp[i-1]，一个cur用来代替被修改的数组元素；

5.2 代码实现

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        int pre = nums[0];
        int cur = 0;
        for(int i = 1; i < ; i++) {
            //更新cur，相当于更新dp[i]
            cur = nums[i] + (pre,0);
            //更新最大值
            res = (res,cur);
            //更新dp[i-1]，使用pre来记录
            pre = cur; 
        }
        return res;
    }
}

5.3 复杂度分析

时间复杂度为O(N)，N为数组中的元素个数；
空间复杂度为O(1)，使用常数大小的额外空间；

六、学习地址

作者：jyd

链接：/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solution/mian-shi-ti-42-lian-xu-zi-shu-zu-de-zui-da-he-do-2/

秒客网