Longest Alternating Subsequence

The idea is to use recursion. Here we have two options that the next element in the sequence should be greater or smaller than the previous element. For this, we will use the indicator to indicate the above condition. 

We will declare a function helper and inside it for every element in the array we have -

• Declare ‘RESULT’ = ‘0’.
• Include this number in the subsequence:
  • If the indicator is ‘1’ and the previous element is less than the current element(i.e. ‘ARR[i - 1]’ < ‘ARR[i]’), include this in the subsequence as next greater.
  • If the indicator is ‘0’ and the previous element is greater than the current element(i.e. ‘ARR[i - 1]' > ‘ARR[i]’), include this in the subsequence as next smaller.
• Recur for the next element by changing the indicator and update the result.
• Exclude this element and recur for the next indicator remaining the same and update result.

Call this helper function in the original function twice, one for the indicator as ‘0’ and one for the indicator as ‘1’ and return the maximum of both values.

We are solving this problem by solving its subproblems and then combining the solutions of those subproblems. If we analyze carefully, we will see that we are solving the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. Thus, in this approach, we will eliminate the need for solving the same subproblems again and again. The idea is to store the answer till the current index and use it for further calls.

Whenever a call is made to the solved subproblem, we will directly return the answer of that subproblem stored in the array.

 The helper function:-

• Use a 2-D array ‘DP[N][2]’ to store the values of calls that are called for the first time in which ‘DP[i][0]’ stores the answer till the current index ‘i’ when the indicator is ‘0’ and ‘DP[i][1]’ stores the answer for the index when the indicator is ‘1’.
• Use a helper function and inside the function:
  • If ‘DP[i][indicator]’ is ‘0’ we will make the calls and declare the result = ‘0’.
  • Include this number in the subsequence-.
    • If the indicator is ‘1’ and the previous element is less than the current element(i.e. ‘ARR[i - 1]’ < ‘ARR[i]’), include this in the subsequence as next greater.
    • If the indicator is ‘0’ and the previous element is greater than the current element(i.e. ‘ARR[i - 1]’ > ‘ARR[i]'), include this in the subsequence as next smaller.
  • Recur for the next element by changing the indicator and update the result.
  • Exclude this element and recur for the next indicator remaining the same and update ‘RESULT’.
  • Update the ‘DP’ array, i.e. ‘DP[i][indicator]’ = ‘RESULT’.
  • Return this ‘DP[i][indicator]’.
• Call this helper function in the original function twice, one for the indicator as ‘0’ and one for the indicator as ‘1’ and return the maximum of both values.

We are solving this problem by solving its subproblems and then combining the solutions of those subproblems. If we analyze carefully, we will see that we are solving the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. Thus, in this approach, we will eliminate the need for solving the same subproblems again and again. The idea is to store the answer till the current index and use it for further calls.

• Use a 2-D array ‘DP[N][2]’ to store the values, in which ‘DP[i][0]’ stores the answer till the current index ‘i’ when ‘ARR[i]’ > ‘ARR[i - 1]’ and ‘DP[i][1]’ stores the answer for the index when ‘ARR[i]’ < ‘ARR[i - 1]’.
• Declare ‘RESULT’ = ‘0’.
• Initialize ‘DP[0][0]’ and ‘DP[0][1]’ as zero as these are the base cases.
• Run two nested loops outer one starting from ‘i’ = ‘0’ to ‘N’ and the inner one starting from ‘j’ = 0 till ‘i’.
• Check if('ARR[i]' > ‘ARR[j]’), store ‘DP[i][0]’ = max('DP[i][0]', ‘DP[j][1]’ + 1);
• Similarly if('ARR[i]' < ‘ARR[j]’), store ‘DP[i][0]’ = max('DP[i][1]', ‘DP[j][0]’ + 1);
• Update the ‘RESULT’ in every iteration.
• Finally, return the ‘RESULT’.

The idea is to solve it without using the extra space in the previous approaches. We were storing the length of the longest alternating subsequence till the index ‘i’ and considering the case that whether the last element is smaller or greater than the previous one.

• To reduce space here, we will take two variables increasing and decreasing for every iteration.
• Increasing will store the length of the longest alternating subsequence so far with the current value being greater than its previous value.
• Decreasing will store the length of the longest alternating subsequence so far with the current value being smaller than its previous value.
• Now we will increment the increasing variable if and only if the last element in the alternating sequence was smaller than its previous element.
• And we will increment the decreasing variable if and only if the last element in the alternating sequence was greater than its previous element.
• Initialize the variables ‘INCREASING’ and ‘DECREASING’  = ‘1’.
• Starting a loop from ‘i’ = 1 till the end of the array.
• Check if the previous element is smaller than the current element then update the increasing variable as in 'INCREASING' = ‘DECREASING’ +  1.
• Similarly, do it for the decreasing variable.
• Finally return the maximum of both variables.