目录
题目描述：
思路一：动态规划
实现代码：
思路二：贪心算法
实现代码：
仅供个人学习使用
题目描述：
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
示例2：
示例3：
思路一：动态规划
如果前一个元素大于0，则加到当前元素上。对于这个问题，我们可以采用以下步骤：
1. 定义状态：
令dp[i]表示以nums[i]结尾的最大子数组和。
2. 状态转移方程：
对于每个i（从1到n-1），dp[i]可以由dp[i-1] + nums[i]得到，如果dp[i-1]是正数，因为加上前面的子数组和会更大。
如果dp[i-1]是负数，那么dp[i]应该直接等于nums[i]，因为加上一个负数的和会减少总和，不如从当前元素开始新的子数组。
3. 初始化和遍历：
初始化dp[0] = nums[0]，因为以第一个元素结尾的子数组和就是它本身。
遍历数组，对于每个元素nums[i]，根据状态转移方程更新dp[i]。
4. 记录最大值：
在遍历的过程中，同时记录下所有dp[i]中的最大值，这个值就是整个数组中的最大子数组和。
5. 优化空间：
- 由于我们只关心以每个元素结尾的最大子数组和，而不是整个数组的子数组和，所以我们可以只使用一个变量
pre来存储dp[i]的值，而不需要一个数组。 - 同时，我们使用另一个变量
maxAns来记录遍历过程中遇到的最大和。
这种方法的核心思想是，对于每个元素，我们考虑两种情况：要么我们将其与前一个元素组合，要么我们不组合。我们总是选择给我们最大和的选项。这样，当我们到达数组的末尾时，我们已经找到了具有最大和的子数组。
实现代码：
class Solution {public int maxSubArray(int[] nums) {int pre = 0,maxAns = nums[0];for(int x:nums){pre = Math.max(x,pre+x);maxAns = Math.max(pre,maxAns);}return maxAns;}
}思路二：贪心算法
若当前指针所指向的元素之前的和小于0，则丢弃当前元素之前的数列。
实现代码：
class Solution {public int maxSubArray(int[] nums) {int sum=0,maxAns=nums[0];for(int x:nums){sum+=x;if(sum>maxAns) maxAns=sum;if(sum<0) sum=0;}return maxAns;}
}