题解 | #最长递增子序列#

class Solution
    def LIS(arr)
        # write code here
        result = [] # 每一次遍历重排后的排序队列
        temp = [] # 记录每个arr中元素在arr中前面有多少位是比它小的（序号）
        (0...arr.length).each{|i|
            if result.length == 0
                result << arr[i]
                temp[i] = 0 # 即第1个数组前面没有比它小的
            else
                if result[-1] < arr[i]
                    result << arr[i]
                    temp[i] = temp[i-1] + 1
                elsif result[-1] > arr[i]
                    if result[0] > arr[i]
                        temp[i] = temp[0]
                        result[0] = arr[0]
                    else
                       (1...result.length).each{|j|
                         if result[result.length-1-j] < arr[i]
                            ole_inx = arr.index(result[result.length-j-1])
                            temp[i] = temp[ole_inx] + 1
                            result[result.length-j] = arr[i]
                            break                              
                         end
                       }
                    end

                end
            end
        }
        
#         p "arr : #{arr}"
#         p "result : #{result}"
#         p "temp : #{temp}"
        # 虽然 result 不是严格排序的， 但result的长度必定与最长递增子序列相等
        # 有多个末位数的递增子序列长度相等，则应取后一位， 因为长度相等后一位的数字肯定更小
        # 但是所取的后一位的数字的序列必须比所有它前面的数据的序列长度要长
        # 综上， 我们从最长序列的末数字从后往前取
        rel_result = []
        len = result.length
        (0...arr.length).each{|i|
            if temp[arr.length-1-i] == len - 1
                rel_result[len-1] = arr[arr.length-1-i]
                len -= 1
            end
        }
        rel_result
    end
end