53. 最大子序和-简单

53. 最大子序和

动态规划 解法

• 时间复杂度 O(n)
  一次遍历，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
• 空间复杂度 O(1)
  只开辟了两个额外的空间，即只需要常数空间存放若干变量。

func maxSubArray(_ nums: [Int]) -> Int {
        // 取nums[0] 为和
        var sum = nums[0]
        // 取nums[0] 为当前最大值
        var ans = nums[0]

        // 因为已经把 nums[0] 计算了，所以从 nums[1] 开始
        for i in 1 ..< nums.count {
            if sum < 0 { // 如果 sum 小于 0 ，那么 sum + nums[i] 只会让 nums[i] 更小
                sum = nums[i] // 所以接把 num[i] 赋值给 sum
            } else {
                // sum >= 0 那么就直接加 nums[i] 不用考虑 nums[i] 是大于零 还是小于零
                sum = sum + nums[i]
            }
            ans = (sum > ans) ? sum : ans
        }
        return ans
    }