53. 最大子数组和

动态规划。dp[i]表示以第i个元素结尾的和的最大值

func maxSubArray(_ nums: [Int]) -> Int {
        let len = nums.count
        if len == 1 {
            return nums[0]
        }
        var dp = Array.init(repeating: 0, count: len)
        dp[0] = nums[0]
        for i in 1..<len {
            
            if dp[i - 1] > 0 {
                dp[i] = dp[i - 1] + nums[i]
            }else {
                dp[i] = nums[i]
            }
        
        }
        return dp.max() ?? dp[0]
        
    }

优化版本

func maxSubArray(_ nums: [Int]) -> Int {
        let len = nums.count
        if len == 1 {
            return nums[0]
        }
        var maxValue = nums[0] ,maxSum = maxValue
        
        for i in 1..<len {
          
            if maxSum > 0 {
                maxSum += nums[i]
            }else {
                maxSum = nums[i]
            }
            maxValue = max(maxSum, maxValue)
          
        }
         return maxValue
        
    }