Swift solution - Divide and Conquer


  • 0
    public struct SubArray {
        var largestSumFirst = 0
        var largestSum = 0
        var largestSumLast = 0
        var sum = 0
        
        public init(_ largestSumFirst: Int, _ largestSum: Int, _ largestSumLast: Int, _ sum: Int) {
            self.largestSumFirst = largestSumFirst
            self.largestSum = largestSum
            self.largestSumLast = largestSumLast
            self.sum = sum
        }
    }
    
    class Solution {
        func maxSubArray(_ nums: [Int]) -> Int {
            let subArray = helper(nums, nums.count)
            return subArray.largestSum
        }
        
        private func helper(_ nums: [Int], _ n: Int) -> SubArray {
            if n == 1 {
                return SubArray(nums[0], nums[0], nums[0], nums[0])
            }
            
            let subArray1 = helper(nums, n / 2)
            let subArray2 = helper(Array(nums[(n / 2)...(n - 1)]), n - n / 2)
            let largestSumFirst = max(subArray1.largestSumFirst, subArray1.sum + subArray2.largestSumFirst)
            let largestSum = max(subArray1.largestSumLast + subArray2.largestSumFirst, max(subArray1.largestSum, subArray2.largestSum))
            let largestSumLast = max(subArray2.largestSumLast, subArray1.largestSumLast + subArray2.sum)
            let sum = subArray1.sum + subArray2.sum
            
            return SubArray(largestSumFirst, largestSum, largestSumLast, sum)
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.