携手创作，共同成长！这是我参与「日新计划 8 月更文应战」的第1天，点击检查活动详情
一、题目
给你一个整数数组 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数组，那么dp[i]就表示以nums[i]结束的子数组最大的和，然后遍历数组核算，回来最终的核算成果即可。初始的话关于nums的第一个元素nums[i]来说其最大值便是自身元素值，因为一个元素也是一个子数组，所以dp[0] = nums[0]。关于其他元素，假如挑选该元从来组成子数组的话，那么最大的子数组和便是以前一个元素结束的子数组之和加上自身元素和即dp[i] = dp[i - 1] + nums[i]；假如不挑选该元素与前面元素组合成子数组，那么最大的元素和便是该元素自身的值即dp[i] = nums[i]，而要取得最大的子数组和就获取两种挑选中成果大的一种。关于dp数组每次核算我们只用到了dp[i - 1]，所以为了优化空间能够直接运用一个变量来代替dp数组来核算也是能够的。
三、代码
办法一
Java代码
class Solution {
public int maxSubArray(int[] nums) {
int dp = 0;
int maxSum = nums[0];
for (int num : nums) {
dp = Math.max(dp + num, num);
maxSum = Math.max(maxSum, dp);
}
return maxSum;
}
}
时刻复杂度：O(n)，需求遍历一次数组元从来核算。
空间复杂度：O(1)，只运用了常数的空间。
