Maximum Subarray in Swift — Kadane's Algorithm (Optimal) & More

Maximum Subarray (#53 — Medium): Given an integer array nums, find the subarray with the largest sum, and return its sum.

Problem Statement

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the sum 6.

Approach: Kadane’s Algorithm (Optimal)

Time: O(n) | Space: O(1)

Kadane’s tracks the best sum ending at each index: either start fresh at current element, or extend the previous sum. The answer is the maximum of all these local bests.

func maxSubArray(_ nums: [Int]) -> Int {
    guard let first = nums.first else { return 0 }
    var maxSum = first, current = first
    for num in nums.dropFirst() {
        current = max(num, current + num)
        maxSum = max(maxSum, current)
    }
    return maxSum
}
print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))  // 6

Approach: Brute Force

Time: O(n²) | Space: O(1)

Try every starting point and extend it to all possible endings. Too slow for large inputs but simple to verify correctness.

func maxSubArrayBrute(_ nums: [Int]) -> Int {
    var maxSum = nums[0]
    for i in 0..<nums.count {
        var current = 0
        for j in i..<nums.count {
            current += nums[j]
            maxSum = max(maxSum, current)
        }
    }
    return maxSum
}

Key Takeaways

• Start with the brute-force approach to understand the problem
• Kadane’s Algorithm (Optimal) gives the optimal O(n) solution
• Practice this pattern — it appears frequently in coding interviews

Related Problems

• Maximum Subarray in Python
• Maximum Subarray in Dart
• Maximum Subarray in Go
• Two Sum in Swift
• Remove Duplicates from Sorted Array in Swift
• Contains Duplicate in Swift

FAQ

What is the best approach to solve Maximum Subarray in Swift?

The recommended approach is Kadane’s Algorithm (Optimal), which runs in O(n) time with O(1) space. The full Swift implementation is shown above.

What is the time complexity of Maximum Subarray in Swift?

Using Kadane’s Algorithm (Optimal), the time complexity is O(n) and the space complexity is O(1).

Happy coding!