1.題目

給你一個整數數組 nums ，請你找出一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

子數組 是數組中的一個連續部分。

示例 1：

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續子數組 [4,-1,2,1] 的和最大，為 6 。

示例 2：

輸入：nums = [1]
輸出：1

示例 3：

輸入：nums = [5,4,-1,7,8]
輸出：23

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

進階：如果你已經實現複雜度為 O(n) 的解法，嘗試使用更為精妙的 分治法 求解。

2.題目分析

     本道題也是一道動態規劃題目。

    設dp[i]為該位置下的最大連續子數組之和。

    dp[i]=nums[i](當nums[i]>(dp[i-1]+nums[i]))

    dp[i]=nums[i]+dp[i-1](當nums[i]<=(dp[i-1]+nums[i]))

  max=dp[i](max<dp[i])

3.代碼

class Solution {
    public int maxSubArray(int[] nums) {
        int length=nums.length;
        int dp[]=new int[length];
        int max=nums[0];
        dp[0]=nums[0];
        if(length ==1)
        {
            return max;
        }
        for(int i=1;i<length;i++)
        {
            int temp=nums[i]+dp[i-1];
            if(nums[i]>(temp))
                dp[i]=nums[i];
            else
                dp[i]=temp;
            if(max<dp[i])
                max=dp[i];
        }
        return max;
    }
}