Subsequence problem

help
1

given an array of size n find largest subsequence array such that its elements follow a pattern

f[i]=f[i-1]+f[i-2]

for eg:
7
6 2 3 4 5 8 13

o/p = 5
subsequence = {2,3,5,8,13}

this problem was asked in infytq certification exam

pls share ur approaches

1 Like
2

It is a nice variation of standard LIS problem, whenever you find a(i)>a(j)…also check if it satisfies the fibonacci condition, by storing previous value of each value :slight_smile:

3

pls can u write its pseudo code it would be really helpful @anon55659401