forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLongestAlternatingSubsequence.java
More file actions
68 lines (50 loc) · 1.71 KB
/
LongestAlternatingSubsequence.java
File metadata and controls
68 lines (50 loc) · 1.71 KB
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
64
65
66
67
68
/*
* Problem Statement: -
* Find Longest Alternating Subsequence
* A sequence {x1, x2, .. xn} is alternating sequence if its elements satisfy one of the following relations :
x1 < x2 > x3 < x4 > x5 < …. xn or
x1 > x2 < x3 > x4 < x5 > …. xn
*/
import java.io.*;
public class LongestAlternatingSubsequence {
/* Function to return longest alternating subsequence length*/
static int AlternatingLength(int arr[], int n){
/*
las[i][0] = Length of the longest
alternating subsequence ending at
index i and last element is
greater than its previous element
las[i][1] = Length of the longest
alternating subsequence ending at
index i and last element is
smaller than its previous
element
*/
int las[][] = new int[n][2]; // las = LongestAlternatingSubsequence
for (int i = 0; i < n; i++)
las[i][0] = las[i][1] = 1;
int result = 1; // Initialize result
/* Compute values in bottom up manner */
for (int i = 1; i < n; i++){
/* Consider all elements as previous of arr[i]*/
for (int j = 0; j < i; j++){
/* If arr[i] is greater, then check with las[j][1] */
if (arr[j] < arr[i] && las[i][0] < las[j][1] + 1)
las[i][0] = las[j][1] + 1;
/* If arr[i] is smaller, then check with las[j][0]*/
if( arr[j] > arr[i] && las[i][1] < las[j][0] + 1)
las[i][1] = las[j][0] + 1;
}
/* Pick maximum of both values at index i */
if (result < Math.max(las[i][0], las[i][1]))
result = Math.max(las[i][0], las[i][1]);
}
return result;
}
public static void main(String[] args)
{
int arr[] = { 10, 22, 9, 33, 49,50, 31, 60 };
int n = arr.length;
System.out.println("Length of Longest "+"alternating subsequence is " +AlternatingLength(arr, n));
}
}