HàPhan 河

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.

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
}

}
``````