Swift 4: Find max sub array. Naive, Kadane, Divide and Conquer

Find max sub array. Naive, Kadane, Divide and Conquer.txt

//
//  main.swift
//  MaxSubArray
//
//  Created by Anthony Marchenko on 10/3/17.
//  Copyright © 2017 Anthony Marchenko. All rights reserved.
//

import Foundation

func maxSubArraySumNaive(_ A: [Int]) -> Int {
    var maxGlobal = 0;
    for i in 0...A.count-1 {
        var maxCurrent = 0
        for j in i...A.count-1 {
            maxCurrent += A[j]
            if maxCurrent > maxGlobal {
                maxGlobal = maxCurrent
            }
        }
    }
    return maxGlobal
}

func maxSubArraySumKadane(_ A: [Int]) -> Int {
    var maxCurrent = A[0]
    var maxGlobal = A[0]
    
    for i in 1...A.count-1 {
        maxCurrent = max(A[i], maxCurrent + A[i])
        if maxCurrent > maxGlobal {
            maxGlobal = maxCurrent
        }
    }
    
    return maxGlobal
}

// 3. Divide and Conquer

func findMaxCrossingSubarray(_ A: [Int], _ low: Int, _ mid: Int, _ high: Int) -> (maxLeft: Int, maxRight: Int, maxSum: Int) {
    var leftSum = Int.min
    var sum = 0
    var maxLeft = Int()
    for i in stride(from: mid, to: low-1, by: -1) {
        sum = sum + A[i]
        if sum > leftSum {
            leftSum = sum
            maxLeft = i
        }
    }
    var rigthSum = Int.min
    sum = 0
    var maxRight = Int()
    
    for j in mid+1...high {
        sum = sum + A[j]
        if sum > rigthSum {
            rigthSum = sum
            maxRight = j
        }
    }
    
    return (maxLeft, maxRight, leftSum + rigthSum)
}

func findMaximumSubarray(_ A: [Int], _ low: Int, _ high: Int) -> (crossLow: Int, crossHigh: Int, crossSum: Int) {
    var leftLow = Int()
    var leftHigh = Int()
    var leftSum = Int()
    var rightLow = Int()
    var rightHigh = Int()
    var rightSum = Int()
    var crossLow = Int()
    var crossHigh = Int()
    var crossSum = Int()
    if high == low {
        return (low, high, A[low])
    } else {
        let mid = Int((low+high)/2)
        (leftLow, leftHigh, leftSum) = findMaximumSubarray(A, low, mid)
        (rightLow, rightHigh, rightSum) = findMaximumSubarray(A, mid+1, high)
        (crossLow, crossHigh, crossSum) = findMaxCrossingSubarray(A, low, mid, high)
        
        if leftSum >= rightSum && leftSum >= crossSum {
            return (leftLow, leftHigh, leftSum)
        } else if rightSum >= leftSum && rightSum >= crossSum {
            return (rightLow, rightHigh, rightSum)
        } else {
            return (crossLow, crossHigh, crossSum)
        }
    }
}

let array = [8, -39, -24, -30, 41, -8, 22, -13, 49, 17, 9, 0, -4, -10, 19, 3, 44, -38, -37, -7, 33, 5, -14, 15, -16, -49, 48, -6, 1, 47, -27, -48, 26, 45, 46, -19, 2, -5, 38, 40, 28, 39, 4, 37, 12, 21, -1, -42, -32, 34, -36, 32, -41, -45, -31, -50, 10, -3, 23, 30, 43, -21, -47, -40, -35, -2, -34, -28, -12, -9, 24, 36, -23, 13, -25, 6, 25, 11, 20, 18, 16, -11, 31, -15, 35, -33, 42, 7, -22, -29, 29, -17, -20, -43, -18, 27, -46, -26, -44, 14];

print("naive - \(maxSubArraySumNaive(array))") // 390
print("Kadane - \(maxSubArraySumKadane(array))")
print("Devide and Conqure - \(findMaximumSubarray(array,0, array.count-1))")