给你一个整数数组
nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
最大子数组和，我们今天从递推——记忆化搜索——动态规划来解决本题
- 递推
假如当前数为1，如果前面的sum和是小于0的是不是有：
数组[-2,1]的子数组和一定比[1]的子数组和小，所以我们就可以推得递推：假如你当前元素前面的子数组和是小于零的，加上当前的值的和一定比当前元素本身的值要小，所以我们取最大的，只取本身这个元素，所以我们就可以推得关系式：
Math.max(nums[i],前面子数组最大和+nums[i]);函数签名：
public int dfs(int i,int[] nums){}函数dfs返回的是当包含索引为i的元素时，子数组的最大和通过for循环，将0~n-1索引的最大子数组和通过比较，找出最大值，就是我们所要的结果
int ans=nums[0];for(int i=1;i<nums.length;i++){ans=Math.max(ans,dfs(i,nums));}递归很明显
因为中间做了很多重复的操作，使得超时，那么我们怎么样才能避免这样重复的操作发生呢？
这个时候我们的记忆化搜索就派上了用场
- 记忆化搜索
记忆化搜索无非就是维护一个数组，将计算后的结果存进数组中，等到计算时，先去数组中找，看是否被计算过，如果计算过，直接在数组中找，如果没有计算，计算之后将结果存进数组中，以便后续的使用
int[] memo;memo=new int[nums.length];Arrays.fill(memo,-1); if(memo[i]!=-1){return memo[i];}memo[i]=Math.max(nums[i],dfs(i-1,nums)+nums[i]);源码如下：
int[] memo;public int maxSubArray(int[] nums) {if(nums==null||nums.length==0){return 0;}memo=new int[nums.length];Arrays.fill(memo,-1);int ans=nums[0];for(int i=1;i<nums.length;i++){ans=Math.max(ans,dfs(i,nums));}return ans;}public int dfs(int i,int[] nums){if(i<0){return 0;}if(memo[i]!=-1){return memo[i];}memo[i]=Math.max(nums[i],dfs(i-1,nums)+nums[i]);return memo[i];}- 动态规划
递归是自顶向下，那么动态规划就是自底向上，通过基础（base）推，这里有个非常高大上的名字就做状态转移方程，其实
Math.max(nums[i],dfs(i-1,nums)+nums[i]);其实递推关系式和我们的状态转移方程在某种意义上来讲是一样的
int[] dp=new int[nums.length];base(当dp[0]时，只有索引为0的元素，自然而然最大值就是nums[0])
dp[0]=nums[0];进行状态转移：
for(int i=1;i<nums.length;i++){dp[i]=Math.max(nums[i],dp[i-1]+nums[i]);}源码如下：
//动态规划public int maxSubArray(int[] nums) {if(nums==null||nums.length==0){return 0;}int[] dp=new int[nums.length];dp[0]=nums[0];for(int i=1;i<nums.length;i++){dp[i]=Math.max(nums[i],dp[i-1]+nums[i]);}int ans=Integer.MIN_VALUE;for(int i=0;i<dp.length;i++){ans=Math.max(dp[i],ans); }return ans;}在这里给大家安利一种比较简便的方法，不用你会动态规划、不用你会记忆化搜素、不用你会递归 所谓的正反馈法
假如现在的一个
假如当前你准备要往子数组[-2,1,-3]中加入元素4，但是原本这个子数组的值是小于0，如果你是这个4，本身自身已经很大了，在这个弱肉强食的时代，你还要带几个拖油瓶去拉低你自己的值，即使没有神一样的队友，也解决不要猪一样的队友，所以不如自己单干，正向反馈类似于这个思想
源代码如下：
public int maxSubArray(int[] nums) {if(nums==null||nums.length==0){return 0;}//正反馈int sum=0;int ans=nums[0];for(int num:nums){//如果之前的和大于0，说明之前的操作对于结果是正反馈if(sum>0){sum+=num;//之前的和小于0，说明之前的操作对于当前结果是负反馈}else{sum=num;}//去中间最大值ans=Math.max(sum,ans);}return ans;}
