Задача: Общая подпоследовательность наибольшей длины

Условие: на вход подаются две строки, необходимо вывести их наидлиннейшую общую подпоследовательность, а точнее ее длину.

Подпоследовательность - совокупность символов, не обязательно смежных, идущих слева направо в том же порядке, что и в исходной строке.

Пример:

Ввод: text1 = "abcde", text2 = "ace" 

Вывод: 3

Объяснение: "ace"

Ввод: text1 = "abc", text2 = "def"

Вывод: 0

Решение:

Сложности

• Временная: 
• Пространственная: 

Код Go

func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    if m < n { // choose n is shorter
        text1, text2, m, n = text2, text1, n, m
    }

    dp := make([]int, n+1)
    for i := 0; i < m; i++ {
        /*    prev         tmp
            dp[i][j]    dp[i][j+1]
            dp[i+1][i]  dp[i+1][j+1]
                    ----->
        */
        prev := 0
        for j := 0; j < n; j++ {
            tmp := dp[j+1]
            if text1[i] == text2[j] {
                dp[j+1] = prev + 1
            } else {
                dp[j+1] = max(dp[j], tmp)
            }
            prev = tmp
        }
    }
    return dp[n]
}

func max(a, b int) int {
    if a < b {
        return b
    }
    return a
}