November 13, 2020   default

Longest Alternating Subarray is a problem of finding a subarray with alternating positive and negative elements, and in which the subarray is as long as possible.

The problem differs from problem of finding Longest Alternating Subsequence, unlike a subsequence, subarray is required to occupy consecutive positions within the original sequences.

For example, consider array { 1, 12, 6, 4, -3, 2, -4,-3. The longest alternating subarray is ( 4, -3, 2, -4) Note that the longest alternating subarray might not be unique

We can easily solve this problem in linear time using similar logic as Kidane's algorithm. The idea to maintain the longest alternating sub-array "ending" at each index of the given array. This subarray can be a single element of a previous element has the same sign) or consists of one more elemments than the longest alternating subarray ending at the previous index (if the previous element has the opposite sign