Longest Increasing Subsequence using Golang

Longest Increasing Subsequence using Golang:

This question most frequently asked in tech companies. Solved this question based on backtracking, with O(n) extra space which used to maintain the sequence count.

Question Link: https://www.interviewbit.com/problems/longest-increasing-subsequence/

Solution:

/**

* @input A : Integer array

*

* @Output Integer

*/

func lis(A []int ) (int) {

tempList := make([]int, len(A)+1)

var finalSize int

for i:=0;i<len(A); i++ {

tempNump := A[i]

maxNum := 1

for j:=i-1;j>=0;j--{

if tempNump > A[j] {

if tempList[j] + 1 > maxNum {

maxNum = tempList[j]+1

}

}

}

tempList[i] = maxNum

if maxNum > finalSize{

finalSize = maxNum

}

}

return finalSize

}