题目描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
样例
-
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 -
示例 2：
输入：nums = [1]
输出：1 -
示例 3：
输入：nums = [0]
输出：0 -
示例 4：
输入：nums = [-1]
输出：-1 -
示例 5：
输入：nums = [-100000]
输出：-100000
- 提示：
1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105
题目评估
知识点：动态规划、数组、分治算法（我目前还没看这个算法在本题中的应用）
难度：简单（今天写写简单的吧~唉~）
分析
这题我以前做过，但是没有写博客记录总结知识点，现在补上。
确定状态：
本题状态为0..i长度的数组中的最大子数组和。
转移方程：
设res为最终的结果，dp为当前状态。
则转移方程为：
dp = max（ nums[i] ， dp + nums[i] ）
res = max（ dp , res ）
初始条件：
res的初值为数组的第一个数：nums[0]。
状态dp的初值为0。
计算顺序：
计算顺序为数组从前往后的顺序。
另外本题还可以使用分治算法来求解，我还没有仔细看这个解题方案，可以参考官方题解方法二
Java代码题解
class Solution {
public int maxSubArray(int[] nums) {
int max = nums[0]; // 最大值 结果
int dp = 0; // 状态
for (int i = 0; i < nums.length; i++) { // 一次遍历数组
// 比较：状态加上当前位置的数组值 和 当前位置的数组值 哪个大就取哪个赋给状态
dp = Math.max(nums[i], dp + nums[i]);
// 比较：状态和当前记录的结果 哪个大就赋给结果
max = Math.max(max , dp);
}
return max;
}
}
复杂度分析
本题一遍遍历数组所以时间复杂度为O(n)。
状态保存为一个变量，所以空间复杂度为O(1)。