# 问题 原题链接：[https://leetcode.com/problems/maximum-subarray/](https://leetcode.com/problems/maximum-subarray/) Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: ``` Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. ``` Follow up: - If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle. # 分析过程 - 输入：一个数组：[−2,1,−3,4,−1,2,1,−5,4] - 输出：子序列的最大和：6 - 思路：遍历数组，某个元素前面的所有元素和小于这个元素的话，就舍弃前面所有的元素，从这个元素开始加，可以保证和最大。 # 解决方法 解法1： ``` swift class Solution { func maxSubArray(_ nums: [Int]) -> Int { var maxSum = Int.min var cur = 0 for i in nums { // 如果和比自己本身就小，则取自己本身 cur = max(cur + i, i) // 更新此时的最大值 maxSum = max(maxSum, cur) } return maxSum } } ``` 解法2： ```swift class Solution { func _maxSubArray(_ arr: [Int], _ left: Int, _ right: Int) -> Int { if left >= right { return arr[left] } // 数组一分为二 let mid = left + (right - left) / 2 // 左边的最大值 let lMax = _maxSubArray(arr, left, mid - 1) // 右边的最大值 let rMax = _maxSubArray(arr, mid + 1, right) // 以下开始计算从中间往两边伸展的数组的最大值 var mMax = arr[mid] var tmp = mMax if left <= mid - 1 { for i in left...mid - 1 { tmp += arr[mid - 1 - i + left] mMax = max(mMax, tmp) } } tmp = mMax if mid + 1 <= right { for i in mid + 1...right { tmp += arr[i] mMax = max(mMax, tmp) } } return max(lMax, rMax, mMax) } func maxSubArray(_ nums: [Int]) -> Int { return _maxSubArray(nums, 0, nums.count - 1) } } ```