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.
Solution: O(n)
Just add each number to the sum and keep track it.
class Solution {
func maxSubArray(_ nums: [Int]) -> Int {
var globalMax = Int.min
var currentMax = 0
for i in 0..<nums.count {
currentMax = max(nums[i], nums[i] + currentMax)
globalMax = max(currentMax, globalMax)
}
return globalMax
}
}
Divide and Conquer : O(nlogn)
Divide array to two parts by middle point.
Result is max of sum of 3 arrays, left one, right one and array cross middle point.
class Solution {
func maxSubArray(_ nums: [Int]) -> Int {
var data = nums
return maxSubHelper(&data, 0, nums.count - 1)
}
func maxThree(_ a: Int, _ b: Int, _ c: Int) -> Int {
return max(a, max(b,c))
}
func maxSubHelper(_ nums: inout [Int], _ low: Int, _ high: Int) -> Int {
if low == high { return nums[low] }
let middle = (low + high) / 2
//Result
return maxThree(maxSubHelper(&nums, low, middle)
, maxSubHelper(&nums, middle + 1, high)
, maxCrossSum(&nums, low, high, middle))
}
func maxCrossSum(_ nums: inout [Int], _ low: Int, _ high: Int, _ middle: Int) -> Int{
var sum = 0
var leftSum = Int.min
for i in stride(from: middle, through: low, by: -1) {
sum += nums[i]
if leftSum < sum {
leftSum = sum
}
}
sum = 0
var rightSum = Int.min
for i in (middle+1)...high {
sum += nums[i]
if rightSum < sum {
rightSum = sum
}
}
return leftSum + rightSum
}
}