动态规划--最大子序和

最大子序和

     题目地址：https://leetcode-cn.com/problems/maximum-subarray/

     给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

     示例:

     输入: [-2,1,-3,4,-1,2,1,-5,4]

     输出: 6

     解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

分析：

    此类题目适合动态规划来处理

     定义数组dp，用来存储到当前位最大的和

     var dp = [Int](reparting: 0, count: nums.count)

     动态规划三部曲

     step1:推导公式

     dp[i] = dp[i-1]+nums[i]，即：nums[i]加入当前连续子序列和

     nums[i], 即：当前位置的值

     题目要求取最大值，所以取二者的较大值： dp[i] = max(dp[i-1]+nums[i], nums[i])

     step2:初始化

     根据递推公式可知，dp[i]依赖于dp[i-1]的状态，dp[0]就是递推公式的基础；dp[0]因为nums[0] ,即：dp[0] = nums[0]

     step3:写循环体

     因为dp[i]依赖于dp[i-1],所以正向便利并且从1开始

具体代码如下：

func maxSubArray(_ nums: [Int]) -> Int {

        let size = nums.count

        var dp = [Int](repeating:0, count: size)

        dp[0] = nums[0]

        var result:Int = dp[0]

        for i  in 1 ..< size {

            dp[i] = max(dp[i-1]+nums[i], nums[i])

            result = max(dp[i], result)

        }

        return result

    }