Swift DSA: Maximum Subarray

Swift: Maximum Subarray Problem

Problem: Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum. A subarray is a contiguous non-empty sequence of elements within an array.

Examples:

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

Input: nums = [1]
Output: 1
Explanation: The single element forms the maximum subarray.

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The entire array forms the maximum subarray.

Swift Solution

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        // Handle edge cases
        guard !nums.isEmpty else { return 0 }
        guard nums.count > 1 else { return nums[0] }
        
        var currentSum = nums[0]
        var maxSum = nums[0]
        
        // Start from second element
        for i in 1.. (sum: Int, start: Int, end: Int) {
        guard !nums.isEmpty else { return (0, 0, 0) }
        
        var currentSum = nums[0]
        var maxSum = nums[0]
        var start = 0
        var end = 0
        var tempStart = 0
        
        for i in 1.. currentSum + nums[i] {
                currentSum = nums[i]
                tempStart = i
            } else {
                currentSum = currentSum + nums[i]
            }
            
            if currentSum > maxSum {
                maxSum = currentSum
                start = tempStart
                end = i
            }
        }
        
        return (maxSum, start, end)
    }
}

// Example usage
let solution = Solution()

// Test Case 1
let nums1 = [-2,1,-3,4,-1,2,1,-5,4]
print(solution.maxSubArray(nums1))  // Output: 6

// Test Case 2
let nums2 = [1]
print(solution.maxSubArray(nums2))  // Output: 1

// Test Case 3
let nums3 = [5,4,-1,7,8]
print(solution.maxSubArray(nums3))  // Output: 23

// Test with indices tracking
let nums4 = [-2,1,-3,4,-1,2,1,-5,4]
let result = solution.maxSubArrayWithIndices(nums4)
print("Max Sum: \(result.sum), Start Index: \(result.start), End Index: \(result.end)")

Explanation

This solution implements Kadane's Algorithm, which is an efficient way to solve the maximum subarray problem. Here's how it works:

Basic Principle:

At each position, we make a choice:

1. Either extend the existing subarray by including the current element

2. Or start a new subarray from the current element

Algorithm Steps:

1. Initialize two variables:

- currentSum: tracks the maximum sum ending at current position

- maxSum: tracks the overall maximum sum found so far

2. For each number in the array:

- Update currentSum by choosing maximum between:

* Current number alone

* Current number plus previous currentSum

- Update maxSum if currentSum is larger

Time Complexity: O(n) where n is the length of the array

Space Complexity: O(1) as we only use two variables

Additional Features:

- The second version (maxSubArrayWithIndices) also tracks the start and end indices of the maximum subarray

- This is useful when you need to know not just the sum but also the actual subarray

Common Variations:

1. Finding the maximum product subarray

2. Finding the maximum sum circular subarray

3. Finding k subarrays with maximum sum

• Whatsapp
• Tweet
• Share
• Share
• Share
• Share

Sign up here with your email