給你一個整數數組?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;}