题目描述

输入一个 非空 整型数组，数组里的数可能为正，也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为O(n)。

样例

输入：[1, -2, 3, 10, -4, 7, 2, -5]

输出：18

Java 代码

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length + 10];
        if(nums == null || nums.length == 0){
            return 0;
        }
        dp[0] = nums[0];//0位置的和就是nums[0]
        for(int i=1; i<nums.length; i++){
            if(dp[i - 1] < 0){//如果之前的最大和小于0，则当前元素本身为最大和
                dp[i] = nums[i];
            }else{
                dp[i] = dp[i-1] + nums[i];//否则当前位置的最大和为前i-1的最大和加当前元素本身
            }
        }

        int max = Integer.MIN_VALUE;
        for(int i=0; i<nums.length; i++){
            max = Math.max(max, dp[i]);//找到0~length的最大连续子数组和
        }
        return max;
    }
}