Longest Consecutive
Have the function LongestConsecutive(arr) take the array of positive integers
stored in arr and return the length of the longest consecutive subsequence (LCS). An
LCS is a subset of the original list where the numbers are in sorted order, from
lowest to highest, and are in a consecutive, increasing order. The sequence does not
need to be contiguous and there can be several different subsequences. For example:
if arr is [4, 3, 8, 1, 2, 6, 100, 9] then a few consecutive sequences are [1, 2, 3,
4], and [8, 9]. For this input, your program should return 4 because that is the
length of the longest consecutive subsequence.
Examples Input: [6, 7, 3, 1, 100, 102, 6, 12] Output: 2
func LongestConsecutive(_ arr: [Int]) -> Int {
var set = Set(arr)
var longestStreak = 0
for num in set {
// Check if num - 1 exists in the set
// If it does, then num cannot be the starting number of a consecutive sequence
if !set.contains(num - 1) {
var currentNum = num
var currentStreak = 1
// Increment currentNum until the consecutive sequence ends
while set.contains(currentNum + 1) {
currentNum += 1
currentStreak += 1
}
// Update longestStreak if currentStreak is longer
longestStreak = max(longestStreak, currentStreak)
}
}
return longestStreak
}
// Test cases
print(LongestConsecutive([4, 3, 8, 1, 2, 6, 100, 9])) // Output: 4
print(LongestConsecutive([6, 7, 3, 1, 100, 102, 6, 12])) // Output: 2
Introduction: The quest for the longest consecutive sequence within an array of positive integers is a captivating challenge in algorithmic problem-solving. In this exploration, we'll delve into the intricacies of identifying and computing the length of the longest consecutive subsequence (LCS) using Swift.
Understanding Longest Consecutive Subsequence: Before delving into the code, let's grasp the essence of the longest consecutive subsequence. An LCS is a contiguous subset of the original array where the numbers ascend sequentially from the lowest to the highest. Remarkably, these sequences need not be contiguous within the array, presenting an intriguing puzzle to solve.
The Swift Solution:
In Swift, we embark on our journey to unlock the secrets of the longest consecutive sequence through a meticulously crafted function - LongestConsecutive. This function, entrusted with an array of positive integers, diligently endeavors to unveil the length of the LCS.
Sign up here with your email
ConversionConversion EmoticonEmoticon