class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        guard let first = nums.first else {
            return 0
        }
        guard nums.count > 1 else {
            return first
        }

        var maxSingle = Int.min
        var maxSoFar = Int.min
        var maxEndingHere = 0

        for num in nums {
            maxEndingHere += num
            if maxEndingHere < 0 {
                maxEndingHere = 0
            }
            else if maxSoFar < maxEndingHere {
                maxSoFar = maxEndingHere
            }
            maxSingle = max(maxSingle, num)
        }
        return max(maxSoFar, maxSingle)
    }
}

/*
Leetcode results:
-------------------------------------------------------------------------------------
Runtime: 36 ms, faster than 92.37% of Swift online submissions for Maximum Subarray.
Memory Usage: 20.9 MB, less than 16.67% of Swift online submissions for Maximum Subarray.
-------------------------------------------------------------------------------------
*/