I am trying to give a simple recursive definition that gives the length of the longest oscillating subsequence of an array. I know that I need to look at both the X[i] and X[i-1] elements, compare them and increment a counter based on what it is. (less than or greater than). I'm not sure how to make it recursive though. Would adding LOS(max(counter1,counter2)) be the correct thing to add after the if statements to make it recursive?
Finding Length of Longest Oscillating Subsequence
Viewed 30
1 Answers
If you want to find the longest length of: X1X3<... or X1>X2... So consider that, max_less is the longest length at index i when X[i - 1] > X[i] and max_more is the longest length at index i when X[i - 1] < X[i]. Loop to the end of array if X[j] > X[j - 1], now max_more = max_less + 1 and vice versa. Return max(max_less, max_more)
Related