给定一个整数数组 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.自己的解法。逐个遍历，然后如果当前子序和大于最大子序和的话，就把当前子序和作为新的最大子序和。然后如果当前子序和是负数的话，就说明这一段子序肯定会影响后面的最大子序和。
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = nums[0];//初始化最大子序和
int currentSum = 0;//初始化当前子序和
for(int i = 0;i < nums.length;i++){//遍历数组
currentSum += nums[i];
if(currentSum > maxSum){//如果当前子序和大于最大子序和
maxSum = currentSum;
}
if(currentSum < 0){//如果当前子序和小于0，就抛弃这部分子序
currentSum = 0;
}
}
return maxSum;
}
}
2.答案解法。利用动态规划。
方程：f(i)=max{f(i−1)+nums[i],nums[i]}
class Solution {
public int maxSubArray(int[] nums) {
int pre = 0, maxAns = nums[0];//初始化当前子序和与最大子序和
for (int x : nums) {//遍历数组
pre = Math.max(pre + x, x);//f(i)=max{f(i−1)+nums[i],nums[i]}
maxAns = Math.max(maxAns, pre);//比较当前子序和与最大子序和
}
return maxAns;
}
}
题源：力扣
