Day 3 of 30 days Leetcode challenge

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.

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
    }
    
}