Techie Delight
Coding made easy
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, -2, 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 kadane’s algorithm. The idea is to maintain longest alternating sub-array “ending” at each index of the given array. This subarray can be single element (if previous element has same sign) or consists of one more elements than the longest alternating subarray ending at the previous index (if previous element has opposite sign).
The algorithm can be implemented as below in C++, Java and Python:
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include <iostream>
#include <algorithm>
using namespace std;
// Utility function to print the subarray arr[i..j]
void printSubArray(int arr[], int i, int j)
{
cout << “{ “;
for (int k = i; k < j; k++) {
cout << arr[k] << “, “;
}
cout << arr[j] << ” }”;
}
// Function to find length of longest subarray with alternating
// positive and negative elements
void findLongestSubArray(int arr[], int n)
{
// stores length of longest alternating subarray found so far
int max_len = 1;
// stores ending index of longest alternating subarray found so far
int ending_index = 0;
// stores length of alternating subarray ending at current position
int curr_len = 1;
// traverse the given array starting from the second index
for (int i = 1; i < n; i++)
{
// if current element has opposite sign than the previous element
if (arr[i] * arr[i – 1] < 0)
{
// include current element in longest alternating subarray ending at
// previous index
curr_len++;
// update result if current sub-array length is found to be greater
if (curr_len > max_len)
{
max_len = curr_len;
ending_index = i;
}
}
// reset length if current element has same sign as previous element
else {
curr_len = 1;
}
}
cout << “The longest alternating subarray is “;
printSubArray(arr, (ending_index – max_len + 1), ending_index);
}
int main()
{
int arr[] = { 1, –2, 6, 4, –3, 2, –4, –3 };
int n = sizeof(arr) / sizeof(arr[0]);
findLongestSubArray(arr, n);
return 0;
}
|
Output:
The longest alternating subarray is { 4, -3, 2, -4 }
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
import java.util.Arrays;
class Main
{
// Function to find length of longest subarray with alternating
// positive and negative elements
public static void findLongestSubArray(int[] arr)
{
// stores length of longest alternating subarray found so far
int maxLen = 1;
// stores ending index of longest alternating subarray found so far
int endIndex = 0;
// stores length of longest alternating subarray ending at current position
int currLen = 1;
// traverse the given array starting from the second index
for (int i = 1; i < arr.length; i++)
{
// if current element has opposite sign than the previous element
if (arr[i] * arr[i – 1] < 0)
{
// include current element in longest alternating subarray ending at
// previous index
currLen++;
// update result if current sub-array length is found to be greater
if (currLen > maxLen)
{
maxLen = currLen;
endIndex = i;
}
}
// reset length if current element has same sign as previous element
else {
currLen = 1;
}
}
int[] subarray = Arrays.copyOfRange(arr, (endIndex – maxLen + 1), endIndex + 1);
System.out.println(“The longest alternating subarray is “
+ Arrays.toString(subarray));
}
public static void main (String[] args)
{
int[] arr = { 1, –2, 6, 4, –3, 2, –4, –3 };
findLongestSubArray(arr);
}
}
|
Output:
The longest alternating subarray is [4, -3, 2, -4]
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
# Function to find length of longest sublist with alternating
# positive and negative elements
def findLongestSubList(A):
# stores length of longest alternating sublist found so far
maxLen = 1
# stores ending index of longest alternating sublist found so far
endIndex = 0
# stores length of longest alternating sublist ending at current position
currLen = 1
# traverse the given list starting from the second index
for i in range(1, len(A)):
# if current element has opposite sign than the previous element
if A[i] * A[i – 1] < 0:
# include current element in longest alternating sublist ending at
# previous index
currLen = currLen + 1
# update result if current sublist length is found to be greater
if currLen > maxLen:
maxLen = currLen
endIndex = i
# reset length if current element has same sign as previous element
else:
currLen = 1
sublist = A[endIndex – maxLen + 1: endIndex + 1]
print(“The longest alternating sublist is:”, sublist)
if __name__ == ‘__main__’:
A = [1, –2, 6, 4, –3, 2, –4, –3]
findLongestSubList(A)
|
Output:
The longest alternating subarray is [4, -3, 2, -4]
Download Run Code
Output:
The longest alternating subarray is { 4, -3, 2, -4 }
Download Run Code
Output:
The longest alternating subarray is [4, -3, 2, -4]
Download Run Code
Output:
The longest alternating subarray is [4, -3, 2, -4]
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).
Because of the way the algorithm uses optimal substructures (the maximum subarray ending at each position is calculated in a simple way from a related but smaller and overlapping subproblem: the maximum subarray ending at the previous position) this algorithm can be viewed as a simple example of Dynamic Programming.