79 · Longest Increasing Subsequence

In an Xcode test target:

import Testing

struct LongestIncreasingSubsequenceTests {

    @Test(arguments: [
        ([2, 8, 3, 7, 1, 9, 4], 4),
        ([9, 1, 4, 2, 3], 3),
        ([5, 5, 5], 1),
    ])
    func returnsTheLengthOfTheLongestStrictlyRisingSelection(numbers: [Int], expected: Int) {
        #expect(lengthOfLIS(numbers) == expected)
    }

    // MARK: - Privates
    private func lengthOfLIS(_ numbers: [Int]) -> Int {
        0
    }
}

In a playground:

func lengthOfLIS(_ numbers: [Int]) -> Int {
    0 // your solution
}

let cases: [([Int], Int)] = [
    ([2, 8, 3, 7, 1, 9, 4], 4),
    ([9, 1, 4, 2, 3], 3),
    ([5, 5, 5], 1),
]
for (numbers, expected) in cases {
    let got = lengthOfLIS(numbers)
    print(got == expected ? "PASS" : "FAIL", numbers, "→", got, "expected", expected)
}

1-D dynamic programming, looking back at every earlier position. The cue is "subsequence" — keep items in order but skip freely — plus "longest". Fix where the chosen sequence ends, and its best length depends only on the best sequences that end at earlier, smaller numbers. Unlike the stairs, the previous step can be any earlier position, so each box looks back at all of them.

Subproblem: the length of the longest rising sequence that ends at position i. Recurrence: that length = 1 + the largest such length at any earlier position whose number is smaller than the number at i (or just 1 if there is none).

Give every position a starting length of 1 — the number on its own. Go through the positions from left to right; for each one, look at every earlier position holding a smaller number and see whether stepping from there makes a longer sequence. The answer is the largest length anywhere, because the best sequence can end at any position, not necessarily the last.

Time O(n²): each position looks back at all earlier ones. Space O(n): one length per position.

func lengthOfLIS(_ numbers: [Int]) -> Int {
    var longestEndingAt = [Int](repeating: 1, count: numbers.count)
    for index in numbers.indices {
        for earlier in 0..<index where numbers[earlier] < numbers[index] {
            longestEndingAt[index] = max(longestEndingAt[index], longestEndingAt[earlier] + 1)
        }
    }
    return longestEndingAt.max() ?? 0
}

The subproblem says "ends at i", which is why the answer is max() over the whole list rather than its last entry. The strict < is what makes [5, 5, 5] answer 1.

Verified with swift test on Swift 6.4 in Swift 6 mode: the three examples above, four more (one number, strictly falling, a rising run of negatives, a longer mixed array), and 3,000 random arrays with many repeats checked against a brute force over every subset. The O(n log n) version below was verified on the same cases.

[2, 8, 3, 7, 1, 9, 4]

Answer 4, found at index 5 — not at the last index, which holds 3.

[5, 5, 5] — no earlier number is strictly smaller, so every length stays 1. Answer 1.

The fast version needs a binary search the standard library doesn't have. The O(n log n) follow-up keeps tails, where tails[k] is the smallest number that can end a rising sequence of length k + 1, and for each number finds the first tail that is ≥ it. tails.firstIndex { $0 >= number } compiles and is correct — and it's a linear scan, so the "fast" version is quietly O(n²) again. The binary search lives in swift-algorithms (partitioningIndex(where:)), which isn't available in a shared editor, so write it:

func lengthOfLISFast(_ numbers: [Int]) -> Int {
    var tails: [Int] = []
    for number in numbers {
        var low = 0, high = tails.count
        while low < high {                       // first tail >= number
            let mid = (low + high) / 2
            if tails[mid] < number { low = mid + 1 } else { high = mid }
        }
        if low == tails.count { tails.append(number) } else { tails[low] = number }
    }
    return tails.count
}

Searching for >= rather than > is what keeps the sequence strictly increasing: an equal number replaces its twin instead of extending past it. And tails is not itself a valid sequence — only its length is meaningful; say that before the interviewer asks.

• "Do it in O(n log n)." → The tails array above: each number either extends the longest sequence or lowers the smallest possible ending of some length, found by binary search.
• "Return the sequence itself." → In the O(n²) version, store for each index the earlier index it extended from, then follow those links back from the index with the largest length.
• "Count how many longest sequences there are (LeetCode 673)." → Carry a count alongside each length: when an earlier position gives a longer length, copy its count; when it ties, add its count.