题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

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

示例 2：

**输入：**nums = [1]
**输出：**1

示例 3：

**输入：**nums = [5,4,-1,7,8]
**输出：**23

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

题解

思路

你选用何种方法解题？ 动态规划

解题过程

这些方法具体怎么运用？
使用dp[i]代表以i结尾的元素最大子数组和；
dp[i]要么包括前一个dp[i-1]要么不包括，因为最大子数组连续，要么和前面相连要么不相连；
所以dp[i] = dp[i-1]+nums[i] 或nums[i]，选最大的一个，
即dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);

dp[i] 不可能包括dp[i-1] 还包括更之前的数，因为如果包含只会变小，不变小的话dp[i-1]就已经包含了。

复杂度

• 时间复杂度: O(n)O(n) O(n)

• 空间复杂度: O(n)O(n) O(n)

Code

class Solution {
 public int maxSubArray(int[] nums) {
 int[] dp = new int[nums.length];
 int max = nums[0];
        dp[0] = nums[0];
  if(nums.length == 0) return 0;
 for(int i = 1;i<nums.length;i++){
 dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
 if(dp[i]>max) max = dp[i];
        }
 return max;
    }
}

#动态规划