Longest alternating subsequence in terms of positive and negative integers

Given an array arr[] of positive and negative numbers only. The task is to find the length of the longest alternating (means negative-positive-negative or positive-negative-positive) subsequence present in the array. 

Examples: 

Input: arr[] = {-4, 3, -5, 9, 10, 12, 2, -1} 
Output: 5 
Explanation: 
The longest sequence is {-4, 3, -5, 9, -1}, which is of length 5. There can be many more subsequences of this length.

Input: arr[] = {10, 12, 2, -1} 
Output: 2 
Explanation: 
The longest sequence is {10, -1}, which is 2. There can be many more subsequences of this length. 

Approach: 
This problem can be solved using Dynamic Programming. It is a variation Longest Increasing Subsequence(LIS). The following are the steps: 

1. For including and excluding an element in the given array arr[] for LAS(Longest Alternative Subsequence), a variable pos is used, when pos = true means the current element needs to be positive and if pos = false then current element needs to be negative.
2. If we include the current element, change the value of pos and recur for the next element because we need the next element of the opposite to the previously included element.
3. Now LAS[i][pos] can be recursively written as: 
   • Base case: If the index called recursively is greater than the last element, then return 0, as there is no such element left to form LAS and if LAS[i][pos] is calculated, then return the value. 

if(i == N) { 
return 0; 
} 
if(LAS[i][pos]) { 
return LAS[i][pos]; 
} 

• Recursive call: If the base case is not met, then recursively call when current element is included and excluded, then find the maximum of those to find LAS at that index. 
   

LAS[i][pos] = Longest Alternating Subsequence at index i by including or excluding that element for the value of pos, 
LAS[i][pos] = max(1 + recursive_function(i+1, pos), recursive_function(i+1, pos));  

• Return statement: At each recursive call(except the base case), return the value of LAS[i][pos]. 
   

return LAS[i][pos];  

1. The LAS for the given array arr[] is the maximum of LAS[0][0] and LAS[0][1].

Below is the implementation of the above approach: 

5

Time Complexity: O(N) where N is the length of the array.

Auxiliary Space: O(n) for call stack

Another approach : Using DP Tabulation method ( Iterative approach )

In this approach we use DP to store computation of subproblems and get the desired output without the help of recursion.

Implementation steps:

• Create a 2D array LAS of size n x 2 to store the lengths of the longest alternating subsequences that end at each index in the array.
• Initialize LAS[0][0] and LAS[0][1] to 1, as the longest alternating subsequence ending at the first index is always of length 1.
• For each pair of indices, check if the subsequence ending at index i can be extended by adding the element at index j. If arr[i] is positive and arr[j] is negative, and if LAS[i][0] < LAS[j][1] + 1, update LAS[i][0] to LAS[j][1] + 1, since adding the element at index j to the subsequence ending at index j will result in a longer alternating subsequence ending at index i
• Similarly, if arr[i] is negative and arr[j] is positive, and if LAS[i][1] < LAS[j][0] + 1, update LAS[i][1] to LAS[j][0] + 1
• Once all possible pairs of indices have been considered, return the maximum value of LAS[n-1][0] and LAS[n-1][1], which represent the lengths of the longest alternating subsequences ending at the last index of the array.

Implementation:

Output:

5

Time Complexity: O(N*N)
Auxiliary Space: O(N*N)